Permutations
Problem Statement
Given an array nums of distinct integers, return all possible permutations. You may return the answer in any order.
Input
An integer array nums where every value is unique.
Output
A list of lists, where each inner list is one ordering that uses every element of nums exactly once.
Constraints
- •
1 <= nums.length <= 6 - •
-10 <= nums[i] <= 10 - •
All integers in nums are distinct
Examples
Example 1
nums = [1,2,3]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]Example 2
nums = [0,1]
[[0,1],[1,0]]Example 3
nums = [1]
[[1]]Learning Objectives
- Recognise that asking for all orderings is the permutation placement pattern.
- Represent the current partial ordering with a path and a **used[]** array.
- Apply choose, explore, and unchoose so sibling branches do not share state.
- Explain why the output size itself is factorial.
Intuition
Pattern Recognition
The phrase all possible permutations means order matters and every element must be used exactly once. This is not a subset problem where each value is either included or skipped once. Instead, every recursion depth represents one position in the output ordering, and the choices are all elements not already used in earlier positions.
Intuition
Think of filling slots from left to right. At depth 0, any number can occupy the first slot. At depth 1, any remaining number can occupy the second slot. A boolean used[] array is the cleanest state because it answers one question in O(1): is this index already in the current path? When the path reaches length n, it is a complete permutation and should be copied into the result.
Common mistakes
- ×Using a start index like combinations, which incorrectly prevents values from appearing before earlier indices.
- ×Adding the live **path** object to the answer without copying it.
- ×Forgetting to unmark **used[i]** after recursion, causing later branches to miss valid choices.
- ×Stopping after one valid ordering instead of collecting every leaf in the recursion tree.
Algorithm Explanation
State
Each recursion frame carries the input nums, a mutable path, a boolean used[] array, and the shared result list. The depth is simply path.length. The invariant is that every index marked true in used[] appears exactly once in path, and every index marked false is available for the next position.
Recursion tree
For nums = [1,2,3], the root is the empty path. Level 1 has branches [1], [2], and [3] because any value can be first. Under [1], the next branches are [1,2] and [1,3]. Their leaves are [1,2,3] and [1,3,2]. The same structure repeats under prefixes [2] and [3]. Every root-to-leaf path is one complete ordering.
Pruning
The only pruning needed for distinct numbers is the used[] check. If an index is already true, choosing it again would duplicate that element inside the same permutation, so the branch is skipped. No value-based duplicate rule is needed because the input values are distinct.
Algorithm
- Create result, path, and used[].
- If path.length == nums.length, copy path into result and return.
- For each index i from left to right, skip it when used[i] is true.
- Choose nums[i] by marking used[i] true and appending it to path.
- Explore the next depth.
- Unchoose by removing the last path value and marking used[i] false.
- Return result after all branches finish.
Solutions
Solution: Backtracking with used array
Fill the permutation one position at a time. At each depth, scan every index and choose only values whose used flag is false. The helper records a copy when the path length reaches the input length, then backtracks so the next sibling branch sees a clean state.
Step-by-step
- Initialise result, an empty path, and a boolean used array of length n.
- In the helper, check whether path.size() == nums.length. If so, copy the path into the result.
- Otherwise, loop over every index because any unused value can occupy the current position.
- Mark the chosen index as used, append its value, and recurse.
- Remove the appended value and mark the index unused before continuing the loop.
O(n! * n)
O(n)
There are n! permutations, and copying each complete path costs O(n). The recursion path and used array take O(n) extra space excluding output.
Java implementation
Dry Run
Sample input
nums = [1,2,3]. Track the first branch completely, then show how backtracking opens the next sibling branches.
| depth | choice | path | used | action |
|---|---|---|---|---|
| 0 | start | [] | [F,F,F] | begin with no chosen values |
| 0 | 1 | [1] | [T,F,F] | choose nums[0] for the first position |
| 1 | 2 | [1,2] | [T,T,F] | choose nums[1] for the second position |
| 2 | 3 | [1,2,3] | [T,T,T] | record a complete permutation |
| 2 | 3 | [1,2] | [T,T,F] | unchoose nums[2] and return to depth 2 |
| 1 | 2 | [1] | [T,F,F] | unchoose nums[1] and try another unused value |
| 1 | 3 | [1,3] | [T,F,T] | choose nums[2] under prefix [1] |
| 2 | 2 | [1,3,2] | [T,T,T] | record the second permutation under prefix [1] |
| 0 | 1 | [] | [F,F,F] | after finishing prefix [1], unchoose nums[0] |
| 0 | 2 | [2] | [F,T,F] | choose nums[1] and repeat the same template |
The tree eventually records six leaves. The key invariant is restored after every return: the path and used[] match the current prefix exactly.
Interview Tips
Say immediately that permutations differ from combinations because order matters, so the loop must start at 0 at every depth. The used[] array prevents reusing an index within the same path, while unchoose restores the frame for the next sibling. Mention the factorial output size so the interviewer knows you are not trying to make the enumeration polynomial.
Likely follow-ups
- How would the solution change if **nums** contained duplicates?
- How would you stream each permutation to a callback instead of storing all of them?
- How would you generate the kth permutation without enumerating every earlier one?
- How would you solve permutations of characters in a string?
Similar Problems
Key Takeaways
- Permutation backtracking fills positions, not include-or-skip decisions.
- Use **used[]** when any unused element can be chosen at every depth.
- Always copy the path at the leaf and always unchoose before the next sibling.
- The honest time bound is **O(n! * n)** because the output has factorial size.