Coding Interview PatternsPermutations
MediumSubsets
Permutations
Explanation & Solution
Description
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Input:nums = [1,2,3]
0
1
1
2
2
3
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Explanation: There are 3! = 6 permutations of three distinct numbers.
Constraints
1 <= nums.length <= 6-10 <= nums[i] <= 10- All the integers of
numsare unique
Approach
Subsets pattern
1. Backtracking Setup
- Initialize an empty
resultarray to collect all permutations - Define a recursive
backtrack(current, remaining)function currentholds the permutation being builtremainingholds the elements not yet used
2. Base Case
- When
remainingis empty, all elements have been placed - Push a copy of
currentintoresult
3. Recursive Choice
- For each element in
remaining, pick it as the next element in the permutation - Add it to
currentand create a newremainingarray without this element - Recurse to fill the next position
4. Backtrack
- After exploring all permutations that start with a given element, remove it from
current(pop) - This restores the state so the next element can be tried at this position
5. Return the Result
- Sort the result lexicographically for consistent output
- Return the complete list of permutations
Key Insight
- At each level of recursion, we choose one of the remaining elements, creating a decision tree with n! leaves
- Unlike subsets, permutations use all elements — the order matters, not the selection
Time
O(n * n!)there are n! permutations and each takes O(n) to copySpace
O(n)recursion depth is nVisualization
Input:
[1, 2, 3]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps