Subsets II
Problem Statement
Given an integer array nums that may contain duplicates, return all possible subsets. The solution set must not contain duplicate subsets, and the order of subsets in the output may be arbitrary.
Input
An integer array nums, where equal values may appear multiple times.
Output
A list of lists containing every distinct subset exactly once.
Constraints
- •
1 <= nums.length <= 10 - •
-10 <= nums[i] <= 10 - •
nums may contain duplicate values
Examples
Example 1
nums = [1,2,2]
[[],[1],[1,2],[1,2,2],[2],[2,2]]Example 2
nums = [0]
[[],[0]]Example 3
nums = [2,2]
[[],[2],[2,2]]Learning Objectives
- Extend the subset DFS template to inputs with duplicate values.
- Sort the array so equal values become adjacent and duplicate branches can be detected locally.
- Use the **i > start** guard to skip only duplicate sibling choices, not valid deeper copies.
- Explain why duplicate pruning removes repeated outputs without removing subsets that need multiple equal values.
Intuition
Pattern Recognition
This is still the subset pattern: enumerate every valid selection, and every recursion node is an answer. The new difficulty is that equal values make different index choices look identical in the output. For [2,2], choosing index 0 alone and choosing index 1 alone both create [2].
Sorting turns duplicate values into adjacent runs. Then each recursion level can enforce one rule: among equal sibling choices, only the first copy is allowed to start a branch. The condition i > start && nums[i] == nums[i - 1] detects exactly that situation. i > start means the previous equal value was available as a sibling in the same frame, so choosing the later copy would duplicate the earlier branch.
The guard must not skip when i == start. In that case, we are in a deeper frame after choosing a previous copy, and selecting the next equal value is how we build valid subsets such as [2,2]. Sorting plus this level-aware guard removes duplicate branches, not duplicate values from the final subsets.
Common mistakes
- ×Skipping every value equal to the previous one, which incorrectly prevents valid subsets like **[2,2]**.
- ×Forgetting to sort first, so equal values are not adjacent and the duplicate check is unreliable.
- ×Using **i > 0** instead of **i > start**, which skips duplicates across different recursion levels and loses answers.
- ×Trying to remove duplicate lists after generation with a set, which hides the real backtracking pruning idea and wastes work.
Algorithm Explanation
State
Each frame carries start and path, just like Subsets. The array is sorted before DFS. At one recursion level, the loop variable i represents sibling choices for the next value to append to path.
Recursion tree
For sorted nums = [1,2,2], the root records []. Choosing 1 records [1]. Inside that branch, choosing the first 2 records [1,2], and the deeper frame may choose the second 2 to record [1,2,2]. After returning to the [1] frame, the loop considers the second 2 as a sibling choice. Because it equals the previous value and i > start, that branch is skipped; it would create another [1,2] branch.
Back at the root, choosing the first 2 records [2], and the deeper frame can choose the second 2 to record [2,2]. When the root loop later considers the second 2, the same skip rule removes it because the first 2 already started the root-level [2] branch.
Pruning
The pruning rule is skip nums[i] when i > start and nums[i] == nums[i - 1]. Sorting makes equal values adjacent. The i > start part proves the previous equal value was a sibling option in this exact frame, so the branch beginning with the later copy would produce the same suffix choices as the branch beginning with the earlier copy. When i == start, the previous equal value belongs to an ancestor choice, not a sibling, so we must allow it to support subsets with multiple copies.
Algorithm
- Sort nums so duplicates are adjacent.
- Create an empty result list and an empty path.
- At the start of every DFS frame, add a copy of path to the result.
- Loop i from start to the end of nums.
- If i > start and nums[i] == nums[i - 1], skip this sibling branch.
- Otherwise choose nums[i], recurse with i + 1, and then unchoose it.
- Return the result after all unique branches have been explored.
Solutions
Solution: Sorted subset DFS with duplicate-sibling pruning
Sort first, then use the normal start-index subset DFS. At each level, skip a value when it is the same as the immediately previous value and the previous value was available as a sibling choice in the same loop.
Step-by-step
- Sort nums so equal values sit next to each other.
- Start DFS with start = 0 and an empty path.
- Record a copy of path at every frame.
- For each candidate index i, skip it if i > start and it equals nums[i - 1].
- Choose nums[i], recurse with i + 1, then remove it before the next sibling.
- Return the accumulated unique subsets.
O(2^n * n)
O(n)
Sorting costs O(n log n), dominated by the worst-case 2^n unique subsets and path copying. Auxiliary recursion space is O(n); output storage can be O(2^n * n).
Java implementation
Dry Run
Sample input
nums = [1,2,2]. After sorting, track how the duplicate-sibling skip keeps one branch for a single 2 while still allowing [2,2] and [1,2,2].
| depth | index considered | path | action | result added |
|---|---|---|---|---|
| 0 | enter start 0 | [] | record current path | [] |
| 0 | choose 1 at 0 | [1] | explore start 1 | pending |
| 1 | enter start 1 | [1] | record current path | [1] |
| 1 | choose first 2 at 1 | [1,2] | explore start 2 | pending |
| 2 | enter start 2 | [1,2] | record current path | [1,2] |
| 2 | choose second 2 at 2 | [1,2,2] | explore start 3 | pending |
| 3 | enter start 3 | [1,2,2] | record current path | [1,2,2] |
| 1 | consider second 2 at 2 | [1] | skip duplicate sibling | none |
| 0 | choose first 2 at 1 | [2] | explore start 2 | pending |
| 1 | enter start 2 | [2] | record current path | [2] |
| 1 | choose second 2 at 2 | [2,2] | explore start 3 | pending |
| 2 | enter start 3 | [2,2] | record current path | [2,2] |
| 0 | consider second 2 at 2 | [] | skip duplicate branch at root | none |
The skip happens only when the later 2 is a sibling of an earlier 2 at the same depth. Deeper frames can still choose the later 2, so subsets with two copies remain valid while duplicate single-copy branches disappear.
Interview Tips
Do not just say skip duplicates. Say exactly where: skip a duplicate only when it appears after the first equal value in the same loop level. The i > start guard is the proof. It distinguishes duplicate sibling branches, which should be removed, from deeper choices that represent taking multiple copies, which must stay.
Likely follow-ups
- How would you adapt this to generate subsets of size exactly **k** with duplicates?
- How would you count the number of unique subsets without listing them?
- How would the duplicate rule change for permutations with repeated values?
- Can you generate the subsets in lexicographic order, and what sort order would you use?
Similar Problems
Key Takeaways
- Sorting makes duplicate values adjacent so a local skip rule can detect repeated branches.
- Use **i > start**, not **i > 0**, to skip duplicate siblings without losing deeper duplicate copies.
- Every recursion node is still a valid subset and should be recorded.
- Pruning duplicate branches is better than generating duplicates and deduplicating afterward.