Pattern visualizer
Permutations
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. Animated on: nums = [1, 2, 3] — generate all 3! = 6 unique permutations..
In-place swap-based permutation backtracking
time O(n * n!)space O(n)step 1 / 12
1
[0]2
[1]3
[2]line 6
backtrack(0): Choose element for position 0. Swap nums[0] with nums[0]=1 (keep 1 at pos 0).
Pseudocode
1FUNCTION permute(nums):2 ans = an empty list of permutations3 FUNCTION backtrack(first):4 IF first === the length of nums: add a copy of nums to ans, then RETURN5 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 FOR10 backtrack(0); RETURN ans
← / → step · space play · Home restart