Subsets II
MediumSort, then skip duplicates at each level
Problem
Return all unique subsets of an array that may contain duplicates.
Sort first, then skip duplicate choices at the same level so each subset appears once.
The idea
With repeated values the plain power set produces duplicate subsets, so sort and, when iterating candidates at a level, skip any value identical to the previous one. That guarantees each distinct multiset is generated exactly once.
The trick
- Sorting is mandatory — the skip relies on equal values being adjacent.
- Skip when `i > start && nums[i] == nums[i-1]`.
- Record at every node, not only at the leaves, if the empty and partial subsets count.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [1,2,2] Values: 1, 2, 2.
1sort(nums)2f(i, cur):3 output cur4 for j from i to n-1:5 if j>i and nums[j]==nums[j-1]: continue6 cur.push(nums[j]); f(j+1, cur); cur.pop()Input
- array
- [1, 2, 2]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 2, 2]
- Output:
- [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
- Explanation:
- Duplicates give unique subsets only.
Example 2
- Input:
- nums = [0]
- Output:
- [[], [0]]
- Explanation:
- {} and {0}.
Example 3
- Input:
- nums = [1, 1]
- Output:
- [[], [1], [1, 1]]
- Explanation:
- {}, {1}, {1,1} — no repeats.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.