Permutations
Understanding the Problem
We need to generate every possible ordering of the input array. A permutation is a rearrangement where order matters. For three elements [1, 2, 3], the arrangements [1, 2, 3] and [2, 1, 3] are different permutations because the elements appear in different positions.
The total number of permutations of n distinct elements is n! (n factorial). For n = 6 (the maximum constraint), that is 720 permutations. So the output itself is at most 720 arrays, which is tiny. The challenge is not efficiency but rather generating every arrangement exactly once without missing any or creating duplicates.
Building a permutation is a sequence of choices. At each position, we pick one of the remaining unused elements and place it there. Once all positions are filled, we have a complete permutation. This "choose from what's left" structure maps onto backtracking.
Key Constraints:
1 <= nums.length <= 6→ With n at most 6, the maximum output is 6! = 720 permutations. The focus is on generating every arrangement exactly once, not on performance.- All integers are unique → We do not need duplicate-handling logic. When the input can contain repeated values, generating distinct permutations requires extra pruning, which is a separate problem.
Approach 1: Backtracking with Used Array
Intuition
Build a permutation one position at a time. With three slots to fill, the first slot can take any of the three elements, the second slot takes one of the two remaining, and the third takes the one left over.
This "pick from what's left" process maps onto backtracking. We maintain the permutation we are building and a record of which elements are still available. At each step, we try every unused element, add it to the current permutation, recurse to fill the next position, then remove it (backtrack) to try the next option.
The backtracking tree has 3 branches at level 1, 2 at level 2, and 1 at level 3, giving us 3 x 2 x 1 = 6 permutations. The total number of leaf nodes is exactly n!.
Algorithm
- Create an empty list to hold the current permutation being built and a boolean array to track which elements are used.
- Define a recursive function that takes the current state.
- If the current permutation has n elements, it is complete. Add a copy to the result and return.
- Otherwise, iterate through all elements. For each unused element, mark it as used, add it to the current permutation, and recurse.
- After the recursive call returns, remove the element from the current permutation and mark it as unused (backtrack).
Example Walkthrough
Code
- Time Complexity: O(n n!). There are n! permutations to generate. For each permutation, we spend O(n) time to copy it into the result. The backtracking explores n (n-1) ... 1 = n! paths, with O(n) work at each node to scan through elements and check the used array.
- Space Complexity: O(n). The recursion stack goes n levels deep. The used array and current list each take O(n) space. We are not counting the output space (which is O(n * n!)).
This approach uses a separate boolean array to track which elements have been placed. The next approach removes that array by using the input array itself to separate placed from available elements.
Approach 2: Backtracking with Swapping (Optimal)
Intuition
Instead of maintaining a separate data structure to track used elements, we can use the input array itself to partition elements into "already placed" and "still available."
At each recursion level, we are filling position index. Everything to the left of index has already been placed. Everything from index onward is still available. To try different elements at position index, we swap nums[index] with each element from index to n-1, recurse to fill the next position, then swap back.
The array serves as both the permutation being built and the pool of available elements, so there is no extra boolean array and no separate current list.
The method rests on an invariant: at any point in the recursion, nums[0..index-1] holds the elements already placed and nums[index..n-1] holds the elements still available. Swapping nums[index] with each element in the available range, including itself, places every available element at position index exactly once, so no permutation is missed or repeated. Swapping back after the recursive call restores the array before the next iteration, which keeps the available range correct for sibling branches.
Algorithm
- Define a recursive function that takes the current index (the position we are filling).
- If the index equals n, all positions are filled. Add a copy of the array to the result.
- Otherwise, for each position j from index to n-1, swap nums[index] with nums[j], recurse with index+1, then swap back.
- The swap puts a different element at the current position each time, and the recursion fills the remaining positions.
Example Walkthrough
Code
- Time Complexity: O(n * n!). Same as Approach 1. We generate n! permutations, and copying each one into the result takes O(n). The swap operations at each node are O(1), but we still visit O(n!) nodes total.
- Space Complexity: O(n). Only the recursion stack, which goes n levels deep. We eliminated the used array and the current list. The input array is modified in-place and restored, so no extra space is needed beyond the stack.