Permutations
Problem
Given an array of distinct integers nums, return all possible permutations of nums in any order.
- 1 ≤ nums.length ≤ 6
- −10 ≤ nums[i] ≤ 10
- All integers in nums are distinct.
Example
nums = [1, 2, 3][[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]The brute-force approach would attempt to generate all permutations by trying every possible ordering, but without pruning or systematic exploration, this can be inefficient and complex to implement. The backtracking approach incrementally builds permutations by choosing elements not yet used, exploring deeper only when the current partial permutation is valid. For example, starting with an empty list, the algorithm picks '1', then recursively picks '2', then '3', forming [1,2,3]. It then backtracks to replace '3' with '3' swapped with '2', forming [1,3,2], and so on, systematically exploring all valid permutations without repetition.
Approach
Straightforward Solution
A naive approach might try to generate all permutations by swapping elements in place or by generating all sequences and filtering duplicates, which is inefficient and error-prone. This approach can lead to redundant work or complex bookkeeping.
Core Observation
Generating permutations requires exploring all possible orderings of the input elements, which is factorial in size. The fundamental truth is that each position in the permutation can be filled by any unused element, and the problem breaks down into choosing an element and recursively permuting the remainder.
Path to Optimal
PreviewThe key insight is to use backtracking with a partial solution that grows by adding unused elements. At each recursive call, the algorithm tries all elements not yet in the current permutation, appends one, and recurses…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a recursive backtracking function that maintains the current permutation path. For each call, iterate over all elements in nums, skip those already in the path, append a new element, recurse, then remove it to backtrack…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n * n!)
There are n! permutations, and each permutation takes O(n) time to construct and copy into the results, leading to O(n * n!) total time.
Space
O(n)
The recursion stack and current path use O(n) space, where n is the length of nums. The output list uses O(n * n!) space but is not counted as auxiliary space.
Pattern Spotlight
Backtracking (State Restoration)
For problems requiring all permutations or combinations, use a 'choose, explore, un-choose' pattern where you add an element to the current path, recurse to explore deeper, then remove the element to restore state for the next choice.
Solution
| 1 | class Solution:
|
| 2 | def permute(self, nums: List[int]) -> List[List[int]]:
|
| 3 | def backtrack(curr):
|
| 4 | if len(curr) == len(nums):
|
| 5 | ans.append(curr[:])
|
| 6 | return
|
| 7 |
|
| 8 | for num in nums:
|
| 9 | if num not in curr:
|
| 10 | curr.append(num)
|
| 11 | backtrack(curr)
|
| 12 | curr.pop()
|
| 13 |
|
| 14 | ans = []
|
| 15 | backtrack([])
|
| 16 | return ans |
Step-by-Step Solution
Accumulate Complete Permutations Upon Reaching Full Length
| 4 | if len(curr) == len(nums):
|
| 5 | ans.append(curr[:])
|
| 6 | return
|
Objective
To detect when a complete permutation has been formed and add a copy to the results list.
Key Insight
The base case of the recursion occurs when the current path length equals the input length, indicating a full permutation. Appending a copy of the current path ensures that subsequent modifications to the path do not affect the stored result. This step is critical to correctly capture each unique permutation.
Interview Quick-Check
Core Logic
Recognize the base case by comparing current path length to input length and append a copy to results to avoid mutation issues.
State & Boundaries
The base case prevents further recursion and signals a valid solution has been found.
Explore Candidates by Adding Unused Elements and Backtracking
To iterate over all input elements, add unused ones to the current path, recurse, and then remove them to restore state.
Initialize Result Container and Launch Backtracking
To prepare the results list and start the recursive backtracking with an empty path.
Return the Complete List of Permutations
To return the accumulated list of all generated permutations after backtracking completes.
3 more steps with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
curr.pop()Remove the last added number to restore the path for the next iteration.
This 'un-choose' step is critical for backtracking, restoring state so other permutations can be explored without interference.
if len(curr) == len(nums):Check if the current permutation has reached the length of the input array.
This base case identifies when a complete permutation has been formed, signaling that the current path is a valid solution to be recorded.
ans.append(curr[:])Append a copy of the current permutation to the results list.
Appending a copy prevents future modifications to the current path from altering stored permutations, preserving correctness.
Full line-by-line criticality + rationale for all 11 lines available on Pro.
Test Your Understanding
Why is it necessary to remove the last element from the current path after each recursive call?
See the answer with Pro.
Related Problems
Backtracking pattern
Don't just read it. Drill it.
Reconstruct Permutations from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Permutations drill