Spot the Duplicates

Consider generating all subsets of 122. There are two 2s in the input.

If we run our standard backtracking (include/exclude each element), we get duplicate subsets. The subset 2 appears twice — once by including the first 2, and again by including the second 2.

Look at the tree below. Tap the leaf nodes you think are duplicates, then check your picks.

[ ]+1-1+2-2+2-2{1,2,2}{1,2}{1,2}{1}{2,2}{2}{2}{ }

Tap the leaf nodes you think produce duplicate subsets.

Skip or Explore?

Trace through subset generation for sorted 122. At each branch point, you see the current element, the previous element, and the value of start.

Apply the rule: if nums[i] === nums[i-1] and i > start, skip. Otherwise, explore.

Pay close attention to the cases where i === start — that is where the subtle distinction lives.

1 / 5sorted input: [1, 2, 2]
1
0
2₁
1
2₂
2
i=0, start=0: element is 1. No previous element exists. Skip or explore?

The Sort-and-Skip Rule

Duplicate subsets arise when the same value appears at the same recursion level. Including 2₁ and excluding 2₂ gives the exact same result as excluding 2₁ and including 2₂. The subtrees are mirror images — they produce identical output.

The fix has two parts:

Step 1: Sort the input. This places equal values next to each other. For 122, sorting is a no-op — it is already sorted. But for 31221, sorting gives 11223, which groups the duplicates.

Step 2: At each recursion level, skip an element if it equals the previous one — but only if you are not on the first choice at that level. The condition is:

nums[i] === nums[i-1] && i > start

The i > start part is the critical detail. Without it, you skip too aggressively and miss valid subsets. With i > 0 instead of i > start, the rule fires even when the duplicate is the first choice at its level — which means it is not actually a duplicate.

The Classic Bug

Here is the single most common bug in backtracking deduplication. Two versions of the skip condition:

  • Condition A: i > 0 && nums[i] === nums[i-1]
  • Condition B: i > start && nums[i] === nums[i-1]

They differ by one word: 0 vs start. One produces 4 subsets (wrong). The other produces 6 (correct).

Both versions are shown below with their outputs. Find the buggy one.

Subsets of [1, 2, 2] — which condition has the bug?

Write the Dedup Code

You traced the skip rule, found the classic bug, and know why i > start matters. Now write the function.

Subsets II: generate all subsets of an array that may contain duplicates. Fill in the three blanks: the sorting prerequisite, the skip condition, and the recursive call.

function subsetsWithDup(nums) {
;
const result = [];
function backtrack(start, path) {
result.push([...path]);
for (let i = start; i < nums.length; i++) {
;// skip duplicates
path.push(nums[i]);// choose
;// explore
path.pop();// un-choose
}
}
backtrack(0, []);
return result;
}

Your Call

Three questions on why duplicates arise, how to eliminate them, and why sorting is required.

Question 1/3
Why duplicates happen

Subsets of 122: why does 12 appear twice without dedup?