How is Combination Sum II different from Combination Sum?

In Combination Sum each candidate is distinct and can be reused, so the recursion continues from i. In Combination Sum II each number is used at most once, so it continues from i + 1, and the input may contain duplicates that must not produce repeated combinations.

Why does `i > start and candidates[i] == candidates[i - 1]` remove duplicates?

After sorting, equal values sit next to each other. At one level of the recursion, starting a combination with the second copy of a value finds exactly the combinations the first copy already found. Skipping it at the same level, but not deeper, removes the repeats while still allowing [1, 1, 6].

Why is sorting required?

Sorting groups duplicates so the skip is one comparison, and it lets the loop break as soon as a candidate exceeds the remaining target, because every later candidate is larger.

Combination Sum II

Find every unique combination that adds up to a target, using each number once: sort, skip repeats on the same level, and break early.

MediumSolve on LeetCode

Problem Understanding

Combination Sum II: given candidates (which may contain duplicates) and a target, return every unique combination whose numbers add up to target. Each number may be used once, and the answer must not contain the same combination twice.

Example: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8 returns [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]].

Attempt 1: Generate Everything, Then Deduplicate

Run the Combination Sum search with i + 1 instead of i, and put each sorted combination in a set. It works, but with many duplicates the search finds the same combination over and over before the set throws the copies away. Better not to generate them at all.

The Intuition: One Value per Level

Sort first. Then think of backtrack(start, remaining) as choosing the next number of the combination from candidates[start:].

If two equal values are both offered at the same level, choosing either one leads to exactly the same set of combinations. So at each level, try each value once:

if i > start and candidates[i] == candidates[i - 1]: continue

The i > start part matters: the first copy at a level is always allowed, which is how [1, 1, 6] still uses both 1s, one per level.

The rest is standard backtracking: break when a candidate exceeds what is left, otherwise append it, recurse from i + 1 so it is used once, and pop it.

Interactive Walkthrough

The sorted candidates are drawn in a row. Values in the current path are shaded, the loop's position is marked i, and a candidate turns red when it is skipped as a duplicate or ends the loop as too big.

Dry Run Table

Input: sorted [1, 1, 2, 5, 6, 7, 10], target 8

First pick	Explored	Found
1 (index 0)	1+1+6, 1+2+5, 1+7	[1, 1, 6], [1, 2, 5], [1, 7]
1 (index 1)	skipped: same value at the same level	—
2	2+6	[2, 6]
5	5 + anything left is too big	—
6, 7	nothing fits	—
10	more than 8: break	—

Four combinations, none repeated.

The Solution Template

Sort, skip same-level duplicates, break when too big, recurse from i + 1.

Combination Sum II Code

1var combinationSum2 = function(candidates, target) {
2    candidates.sort((a, b) => a - b);
3    const out = [], path = [];
4    const backtrack = (start, remaining) => {
5        if (remaining === 0) {
6            out.push([...path]);
7            return;
8        }
9        for (let i = start; i < candidates.length; i++) {
10            if (i > start && candidates[i] === candidates[i - 1]) continue;
11            if (candidates[i] > remaining) break;
12            path.push(candidates[i]);
13            backtrack(i + 1, remaining - candidates[i]);
14            path.pop();
15        }
16    };
17    backtrack(0, target);
18    return out;
19};

Edge Cases & Common Mistakes

Skipping with i > 0 instead of i > start: that also skips the second 1 one level deeper and loses [1, 1, 6].
Recursing from i: that reuses the same number; Combination Sum II needs i + 1.
Forgetting to sort: duplicates are no longer adjacent and the early break is wrong.
No combination: return an empty list, as for [3, 5] with target 4.

Summary

Sort, then backtrack from start: skip a value already tried at this level (i > start and equal to its left neighbour), break when a value exceeds what is left, and recurse from i + 1 so each number is used once. No set is needed to remove duplicates.

More practice: DSA interview questions with answers · patterns cheat sheet

Combination Sum

Generate Parentheses