Coding Interview PatternsPermutations II
MediumSubsets
Permutations II
Explanation & Solution
Description
Given a collection of numbers nums that might contain duplicates, return all possible unique permutations in any order.
Input:nums = [1,1,2]
0
1
1
1
2
2
Output: [[1,1,2],[1,2,1],[2,1,1]]
Explanation: Although there are two 1s, only three unique permutations exist.
Constraints
1 <= nums.length <= 8-10 <= nums[i] <= 10
Approach
Subsets pattern
1. Sort the Input
- Sort
numsin ascending order so that duplicate values are adjacent - This is essential for the duplicate-skipping logic to work correctly
2. Track Used Elements
- Maintain a
usedboolean array to track which elements are currently in the permutation - This replaces the "remaining" array approach used in basic Permutations
3. Duplicate Skipping Condition
- When iterating through elements to place at the current position:
- Skip if
used[i]is true (element already in current permutation) - Skip if
nums[i] === nums[i - 1]and!used[i - 1]— this means the previous duplicate was not used, so we would generate a duplicate permutation - The condition
!used[i - 1]ensures we always use duplicate values in order (left to right), preventing repeated branches
4. Build the Permutation
- Mark
used[i] = true, pushnums[i]tocurrent, and recurse - After recursion, pop the element and mark
used[i] = false(backtrack)
5. Return the Result
- Sort the result lexicographically for consistent output
- Return the complete list of unique permutations
Key Insight
- The key to avoiding duplicates is: among identical values, always pick them in left-to-right order
- If
nums[i] === nums[i-1]andused[i-1]is false, skippingnums[i]prevents generating the same permutation from a different copy of the same value
Time
O(n * n!) in the worst case (all unique elements)Space
O(n) for the recursion stack and the `used` arrayVisualization
Input:
[1, 1, 2]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps