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
The 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. When the permutation length equals the input length, a complete permutation is found and added to the results. Backtracking removes the last element before trying the next candidate, restoring state for the next exploration. This approach systematically explores the solution space without duplicates and with clear state management.
Optimal Approach
Use 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. This ensures all permutations are generated exactly once. The algorithm runs in O(n * n!) time, which is optimal for generating all permutations.
Time
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 |
| 1 | import java.util.ArrayList; |
| 2 | import java.util.List; |
| 3 | |
| 4 | public class Solution { |
| 5 | public List<List<Integer>> permute(int[] nums) { |
| 6 | List<List<Integer>> ans = new ArrayList<>(); |
| 7 | backtrack(nums, new ArrayList<>(), ans); |
| 8 | return ans; |
| 9 | } |
| 10 | |
| 11 | private void backtrack(int[] nums, List<Integer> curr, List<List<Integer>> ans) { |
| 12 | if (curr.size() == nums.length) { |
| 13 | ans.add(new ArrayList<>(curr)); |
| 14 | return; |
| 15 | } |
| 16 | |
| 17 | for (int num : nums) { |
| 18 | if (!curr.contains(num)) { |
| 19 | curr.add(num); |
| 20 | backtrack(nums, curr, ans); |
| 21 | curr.remove(curr.size() - 1); |
| 22 | } |
| 23 | } |
| 24 | } |
| 25 | } |
| 1 | #include <vector> |
| 2 | #include <algorithm> |
| 3 | |
| 4 | using namespace std; |
| 5 | |
| 6 | class Solution { |
| 7 | public: |
| 8 | vector<vector<int>> permute(vector<int>& nums) { |
| 9 | vector<vector<int>> ans; |
| 10 | vector<int> curr; |
| 11 | backtrack(nums, curr, ans); |
| 12 | return ans; |
| 13 | } |
| 14 | |
| 15 | private: |
| 16 | void backtrack(const vector<int>& nums, vector<int>& curr, vector<vector<int>>& ans) { |
| 17 | if (curr.size() == nums.size()) { |
| 18 | ans.push_back(curr); |
| 19 | return; |
| 20 | } |
| 21 | |
| 22 | for (int num : nums) { |
| 23 | if (find(curr.begin(), curr.end(), num) == curr.end()) { |
| 24 | curr.push_back(num); |
| 25 | backtrack(nums, curr, ans); |
| 26 | curr.pop_back(); |
| 27 | } |
| 28 | } |
| 29 | } |
| 30 | }; |
| 1 | var permute = function(nums) { |
| 2 | const ans = []; |
| 3 | const backtrack = (curr) => { |
| 4 | if (curr.length === nums.length) { |
| 5 | ans.push(curr.slice()); |
| 6 | return; |
| 7 | } |
| 8 | for (const num of nums) { |
| 9 | if (!curr.includes(num)) { |
| 10 | curr.push(num); |
| 11 | backtrack(curr); |
| 12 | curr.pop(); |
| 13 | } |
| 14 | } |
| 15 | }; |
| 16 | backtrack([]); |
| 17 | return ans; |
| 18 | }; |
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
| 8 | for num in nums:
|
| 9 | if num not in curr:
|
| 10 | curr.append(num)
|
| 11 | backtrack(curr)
|
| 12 | curr.pop()
|
Objective
To iterate over all input elements, add unused ones to the current path, recurse, and then remove them to restore state.
Key Insight
At each recursion level, the algorithm tries every element not already in the current path, ensuring no duplicates in the permutation. Adding an element extends the partial solution, and recursion explores deeper permutations. The pop operation after recursion is the 'un-choose' step that restores the path to its previous state, enabling exploration of alternative branches. This pattern guarantees exhaustive and non-redundant exploration of all permutations.
Interview Quick-Check
Core Logic
Use a for loop to try all elements not in the current path, append one, recurse, then pop to backtrack.
Common Pitfalls & Bugs
Failing to pop after recursion leads to incorrect paths and duplicates.
State & Boundaries
The 'if num not in curr' condition ensures elements are not reused in the same permutation.
Initialize Result Container and Launch Backtracking
| 14 | ans = []
|
| 15 | backtrack([])
|
Objective
To prepare the results list and start the recursive backtracking with an empty path.
Key Insight
Initializing an empty list to store permutations is essential for collecting results. Starting the recursion with an empty path represents the initial state before any elements are chosen. This setup cleanly separates initialization from recursive exploration.
Interview Quick-Check
Core Logic
Initialize an empty list to store permutations and start recursion with an empty current path.
Return the Complete List of Permutations
| 16 | return ans |
Objective
To return the accumulated list of all generated permutations after backtracking completes.
Key Insight
Returning the results list after the recursive calls ensures the caller receives all permutations generated by the backtracking process. This final step completes the algorithm.
Interview Quick-Check
Core Logic
Return the results list containing all permutations after recursion finishes.
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.
if num not in curr:Check if the current number is already in the current permutation path.
This condition prevents reuse of the same element in a single permutation, maintaining the uniqueness constraint.
backtrack(curr)Recursively explore permutations with the updated path.
This recursive call advances the search, building permutations by adding one element at a time.
returnReturn to stop further recursion once a complete permutation is recorded.
This return prevents unnecessary exploration beyond a complete permutation, ensuring the recursion unwinds correctly.
curr.append(num)Add the current number to the permutation path.
Appending the number extends the partial solution, allowing deeper exploration of permutations including this element.
for num in nums:Iterate over each number in the input array to consider it for the current position.
This loop explores all possible candidates for the next position in the permutation, enabling exhaustive search.
backtrack([])Start the backtracking process with an empty current path.
This initial call triggers the recursive exploration of all permutations from an empty state.
ans = []Initialize the list to store all permutations.
This list accumulates all valid permutations found during recursion, serving as the final output container.
return ansReturn the list of all generated permutations.
This return statement provides the final answer after all recursive exploration completes.
Test Your Understanding
Why is it necessary to remove the last element from the current path after each recursive call?
Removing the last element restores the state of the current path so that the algorithm can explore other permutations without carrying over choices from previous branches, ensuring correct and complete exploration of all permutations.
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