Permutations
Last Updated: April 1, 2026
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.
The key observation is that 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 perfectly to backtracking.
Key Constraints:
1 <= nums.length <= 6→ With n at most 6, the maximum output is 6! = 720 permutations. Any approach, even brute force, will run in microseconds. The focus is on correctness and clean generation, not performance optimization.-10 <= nums[i] <= 10→ Small value range, but since all integers are unique, duplicates are not a concern.- All integers are unique → This simplifies things significantly. We do not need duplicate-handling logic (that is LeetCode #47, Permutations II).
Approach 1: Backtracking with Used Array
Intuition
The most natural way to think about generating permutations is to build them one position at a time. Imagine you have three slots to fill: _. For the first slot, you can pick any of the three elements. For the second slot, you pick from the two remaining. For the third, there is only one left.
This "pick from what's left" process is exactly what backtracking does. We maintain a current permutation that we are building and a way to know 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, and 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 works perfectly but uses a separate boolean array to track which elements have been placed. What if we could eliminate the used array entirely by using the input array itself to partition placed and 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, and then swap back.
This is elegant because the array itself serves as both the permutation being built and the pool of available elements. No extra boolean array, no separate current list. Just the array and swaps.
The swap-based approach works because of a clean invariant: at any point during the recursion, nums[0..index-1] holds the elements we have already placed, and nums[index..n-1] holds the elements still available. By swapping nums[index] with each element in the available range, we try every possible element at position index. After the recursive call, we swap back to restore the array, ensuring other branches of the recursion see the original order.
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.