Subsets II
List every subset of an array that may contain duplicates, each exactly once: sort, then skip a repeated value at the same level.
Problem Understanding
Subsets II: given an array that may contain duplicates, return every possible subset, without repeating any subset.
Example: [1, 2, 2] returns [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]. Note [1, 2] appears once, even though there are two 2s to build it from.
The Intuition: Choose Each Value Once per Level
Start from the Subsets template: backtrack(start) records the current path, then tries each nums[i] from start as the next element.
With duplicates, two equal values offered at the same level lead to identical subtrees. After sorting, those copies are adjacent, so one check removes the repeats:
if i > start and nums[i] == nums[i - 1]: continue
The first copy at each level is still tried, and the recursion from it can still pick the next copy one level down. That is how [2, 2] survives while a second [2] does not. The same rule powers Combination Sum II.
Interactive Walkthrough
The sorted numbers are drawn in a row. The current subset is shaded, the number just added is filled, and a repeat skipped at its level is outlined red. Each recorded subset appears in the list beside it.
Dry Run Table
Input: [1, 2, 2] (already sorted)
| Path | Recorded | Next choices |
|---|---|---|
| [] | [] | 1, 2 (second 2 skipped) |
| [1] | [1] | 2 (second 2 skipped) |
| [1, 2] | [1, 2] | 2 |
| [1, 2, 2] | [1, 2, 2] | none |
| [2] | [2] | 2 |
| [2, 2] | [2, 2] | none |
Six subsets: 2 choices for the 1 × 3 for the 2s.
The Solution Template
Sort, record every path, skip same-level repeats.
Subsets II Code
1var subsetsWithDup = function(nums) {2 nums.sort((a, b) => a - b);3 const out = [], path = [];4 const backtrack = (start) => {5 out.push([...path]);6 for (let i = start; i < nums.length; i++) {7 if (i > start && nums[i] === nums[i - 1]) continue;8 path.push(nums[i]);9 backtrack(i + 1);10 path.pop();11 }12 };13 backtrack(0);14 return out;15};
Edge Cases & Common Mistakes
- The empty subset: it is part of the answer; recording before the loop includes it.
i > 0instead ofi > start: that blocks the second copy even one level deeper, losing[2, 2].- Forgetting to sort: equal values are not adjacent, so the neighbour check misses repeats.
- Deduplicating with a set of tuples: it works, but still explores every repeated branch; the skip never builds them.
Summary
Sort, record the path at every call, and skip nums[i] when i > start and it equals nums[i − 1]. Each value is tried once per level, so every subset is built exactly once. O(n · 2^n) time in the worst case.
More practice: DSA interview questions with answers · patterns cheat sheet