Coding Interview PatternsSubsets II
MediumSubsets
Subsets II
Explanation & Solution
Description
Given an integer array nums that may contain duplicates, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Input:nums = [1,2,2]
0
1
1
2
2
2
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Explanation: The subsets are generated while skipping duplicates. For instance, [2] appears only once even though 2 appears twice in the input.
Constraints
1 <= nums.length <= 10-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. Backtracking with Duplicate Skipping
- Use the same backtracking template as the basic Subsets problem
- At each level of recursion, iterate from
startto end of array - Key difference: if
i > startandnums[i] === nums[i - 1], skip this element - This prevents choosing the same value twice at the same decision level
3. Why the Skip Condition Works
- When
i === start, we are free to picknums[i]regardless of duplicates - When
i > startandnums[i] === nums[i - 1], it means we already explored a branch that included this same value at this decision point - Skipping it avoids generating a duplicate subset
4. Record Every Valid Subset
- At the start of each recursive call, push a copy of
currentintoresult - This captures subsets of all sizes including the empty set
5. Return the Result
- Sort the result lexicographically for consistent output
- Return the complete list of unique subsets
Key Insight
- Sorting the array first groups duplicates together, enabling an O(1) duplicate check
- The condition
i > start && nums[i] === nums[i - 1]is the classic technique for avoiding duplicate combinations in backtracking
Time
O(n * 2^n) in the worst case (all unique elements)Space
O(n) for the recursion stackVisualization
Input:
[1, 2, 2]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps