nums, sorted blue = taken on this path · faded = skipped · i points at the next decision
subset the partial answer on the current path
decision tree left edge takes nums[i] · right edge skips its whole run · dashed “dup” nodes are pruned
res 0 subsets
List<List<Integer>> res = new ArrayList<>();int[] nums;public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); this.nums = nums; backtrack(0, new ArrayList<>()); return res;}private void backtrack(int i, List<Integer> subset) { if (i == nums.length) { res.add(new ArrayList<>(subset)); return; } subset.add(nums[i]); // take nums[i] backtrack(i + 1, subset); subset.remove(subset.size() - 1); while (i + 1 < nums.length && nums[i] == nums[i + 1]) { i++; // skip the whole run } backtrack(i + 1, subset);}
- i
- —
- subset
- []
- pruned
- 0
- res.size()
- 0
Why it works
- Brute force dedupes at the end. Build all 2ⁿ subsets as in Subsets, sort each one and drop repeats with a
Set<List<Integer>>. Same O(n · 2ⁿ) bound, but it wastes work on every copy and needs the extra set. - Sorting puts equal values in one run. At a run of
kequal values the only real choice is how many copies to take: 0, 1, …, k. The left branch takes one more copy; the right branch takes no more of them, so it jumps past the whole run. - Each distinct subset is one leaf. Pruning removes exactly the branches that would rebuild a subset already found, so the work is proportional to the output: O(n · 2ⁿ) in the worst case (all values distinct), O(n) stack.
- Pitfall: skip the run only in the skip branch. Skipping duplicates before the take branch loses subsets like
[2,2]. And withoutArrays.sort(nums)equal values are not adjacent, so the while loop misses them. - Related, Combination Sum II (40): the same sort-and-skip-the-run trick removes duplicate combinations.