Permutations

In-place swap-based permutation backtracking

time O(n * n!)space O(n)

To generate every ordering without extra space for a "visited" set, we use in-place swapping. At recursion depth first, every element from index first to n-1 is a candidate to occupy the current slot. We swap candidates[i] into nums[first], recurse to solve the remaining positions first+1..n-1, and then swap back (backtrack) to restore the array before trying the next candidate. When first reaches n, the array is a complete, unique permutation.

Details

Animated on: nums = [1, 2, 3] — generate all 3! = 6 unique permutations.

Problem:PermutationsMedium

Pattern:Backtracking Basics

In-place swap-based permutation backtracking

step 1 / 12

[0]

[1]

[2]

backtrack(0): Choose element for position 0. Swap nums[0] with nums[0]=1 (keep 1 at pos 0).

first=0· arr[0] = 1
i=0· arr[0] = 1

Pseudocode

1FUNCTION permute(nums):
2  ans = an empty list of permutations
3  FUNCTION backtrack(first):
4    IF first === the length of nums:  add a copy of nums to ans, then RETURN
5    FOR i from first to the length of nums - 1:
6      swap nums[first] and nums[i]
7      backtrack(first + 1)
8      swap nums[first] and nums[i]   (undo the swap)
9    END FOR
10  backtrack(0); RETURN ans

← / → step · space play · Home restart

Every step in words

Show all 12 steps

backtrack(0): Choose element for position 0. Swap nums[0] with nums[0]=1 (keep 1 at pos 0).
backtrack(1): Position 0 is fixed as 1. Swap nums[1] with nums[1]=2. Recurse.
first=3 reaches length. Record permutation #1: [1, 2, 3].
Back at first=1: try next candidate i=2. Swap nums[1] and nums[2] → [1, 3, 2]. Recurse.
first=3 reaches length. Record permutation #2: [1, 3, 2].
Backtrack to first=0. Swap nums[0] and nums[1]=2 → [2, 1, 3]. Now 2 is fixed at position 0.
Recurse with 1 at pos 1. Leaf reached: record permutation #3: [2, 1, 3].
Back at first=1: swap nums[1] and nums[2] → [2, 3, 1]. Leaf reached: record permutation #4: [2, 3, 1].
Backtrack to first=0. Swap nums[0] with nums[2]=3 → [3, 2, 1]. Fix 3 at position 0.
Recurse with 2 at pos 1. Leaf reached: record permutation #5: [3, 2, 1].
Back at first=1: swap nums[1] and nums[2] → [3, 1, 2]. Leaf reached: record permutation #6: [3, 1, 2].
Backtracking complete. All 6 permutations generated: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,2,1], [3,1,2]].

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Permutations in the editor All Backtracking problems Back to roadmap