#90 Subsets II
the problem
In plain words
Same as Subsets, but nums may contain duplicates. Return all subsets without duplicate subsets, in any order.
in nums = [1,2,2]
out [[],[1],[1,2],[1,2,2],[2],[2,2]]
in nums = [0]
out [[],[0]]
- 1 ≤ nums.length ≤ 10
- -10 ≤ nums[i] ≤ 10
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBacktracking: subsets
Sort so equal values are neighbours. At one depth, choosing the 2nd copy of a value builds exactly the same subtree as choosing the 1st — so skip it.
solutions
From brute force to optimal
Sort, enumerate all 2ⁿ masks, and keep a HashSet of the resulting lists.
- Sort nums (so equal subsets become equal lists).
- For each mask build the subset.
- Add it only if the set hasn't seen it.
Every mask is built and hashed, including all the duplicates.
The HashSet stores every distinct subset again.
class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); // equal subsets now look identical Set<List<Integer>> seen = new HashSet<>(); List<List<Integer>> result = new ArrayList<>(); for (int mask = 0; mask < (1 << nums.length); mask++) { List<Integer> subset = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { if ((mask & (1 << i)) != 0) subset.add(nums[i]); } if (seen.add(subset)) result.add(subset); // add() returns false for a repeat } return result; }}Same backtracking as Subsets, plus if (i > start && nums[i] == nums[i-1]) continue;.
- Sort nums.
- Record path.
- Loop i from start; skip a value equal to its left neighbour at this depth.
- Choose, recurse(i + 1), un-choose.
Worst case (all distinct) is the same as Subsets; duplicate branches are never entered.
Recursion depth and path (excluding output); no Set.
class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); // duplicates become neighbours List<List<Integer>> result = new ArrayList<>(); backtrack(nums, 0, new ArrayList<>(), result); return result; } private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> result) { result.add(new ArrayList<>(path)); for (int i = start; i < nums.length; i++) { if (i > start && nums[i] == nums[i - 1]) continue; // same value, same level → skip path.add(nums[i]); backtrack(nums, i + 1, path, result); path.remove(path.size() - 1); } }}Dry run
in the room
How to say it in the interview
talk track
- Say why
i > startand noti > 0: the first copy at each depth is allowed, so [2, 2] still appears. - Point out that the Set version still explores every duplicate — the skip avoids that work entirely.
traps
- Skipping with
i > 0(loses [1,2,2]). - Forgetting to sort first.
what they ask next
Follow-ups
Permutations II (LC 47) — same idea for permutations?
Sort, use used[], and skip nums[i] if it equals nums[i-1] and !used[i-1] — equal values are then always used left to right.
before you submit
Edge cases to test
- All equal, like [2, 2, 2] → 4 subsets: [], [2], [2,2], [2,2,2].
- Duplicates far apart in the input ([4, 4, 4, 1, 4]): sorting brings them together.
- No duplicates at all → the same 2ⁿ subsets as LC 78.
practise next
Similar problems
- #78SubsetsMediumin Backtracking
- #40Combination Sum IIMediumin Backtracking
- #46PermutationsMediumin Backtracking