Combination Sum II

1. Problem & Core Objective

Given a collection of candidates (which may contain duplicates) and a target, find all unique combinations summing to the target. Each candidate may be used at most once.

candidates = [10,1,2,7,6,1,5], target = 8
→ [[1,1,6], [1,2,5], [1,7], [2,6]]

candidates = [2,5,2,1,2], target = 5
→ [[1,2,2], [5]]

Constraints: 1 <= candidates.length <= 100 · 1 <= candidates[i] <= 50 · 1 <= target <= 30

What's actually being tested: composing three independent modifications of the base template — no reuse, duplicate skipping, and sum pruning. Nothing here is new; the question is whether you can apply all three without them interfering.

2. First-Principles Thought Process

It's the previous three questions, combined

The sort serves all three purposes: it makes duplicates adjacent for the skip, and it makes the break valid for the pruning.

The distinction that matters most

[1,1,6] is a valid answer even though 1 appears twice — because the input contains two separate 1s at different indices. Using both is legitimate.

What's forbidden is using the same index twice, and generating the same multiset by two different paths.

So the two 1s are:

• allowed together in one combination — they're distinct elements
• not allowed as siblings at the same level — that would build two identical subtrees

The i > start guard draws exactly that line, which is why it's the same guard as Subsets II.

Why i + 1 and the skip don't conflict

They're different mechanisms. i + 1 stops one element being reused; the skip stops one value being tried twice at the same level.

On sorted [1,1,6] with target 8: at depth 0 the loop picks index 0 (value 1) and recurses with start = 1. At depth 1, i = 1 equals start, so the guard doesn't fire — the second 1 is allowed, giving [1,1]. Back at depth 0, the loop reaches i = 1; now i > start and it's a duplicate, so it's skipped.

Exactly the right behaviour, and it falls out of the two rules without any coordination.

3. Solution Paths

Approach 1 — Backtrack without the skip, deduplicate at the end (brute force)

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    Set<List<Integer>> seen = new LinkedHashSet<>();
    backtrack(candidates, 0, target, new ArrayList<>(), seen);
    return new ArrayList<>(seen);
}

private void backtrack(int[] c, int start, int remaining,
                       List<Integer> path, Set<List<Integer>> seen) {
    if (remaining == 0) { seen.add(new ArrayList<>(path)); return; }

    for (int i = start; i < c.length; i++) {
        if (c[i] > remaining) break;
        path.add(c[i]);
        backtrack(c, i + 1, remaining - c[i], path, seen);
        path.remove(path.size() - 1);
    }
}

• Time exponential, with duplicate subtrees fully explored · Space O(results)

Counter-questions on this approach

⭐ "What does the Set cost you?"

Every duplicate branch is explored to completion before the result is discarded. With [1,1,1,1,1] and target 3, the search produces [1,1,1] ten different ways — once per choice of three indices from five — and the Set keeps one.

Pruning at the branch point avoids entering nine of those subtrees at all. And the deeper the duplication, the worse the ratio gets.

⭐ "Is the Set even reliable here?"

Only because I sorted first. Set<List<Integer>> uses List.equals, which is order-sensitive — without the sort, [2,1] and [1,2] would both survive as distinct entries.

So the sort is load-bearing in the brute force too. That's a hint that the sort belongs in the algorithm rather than as a fix-up.

"Would using a Set ever be the right call?"

If the deduplication rule were genuinely hard to express as a branch condition — say the equivalence involved something other than value equality. Here it's one continue, so there's no reason.

Approach 2 — Sort, skip siblings, prune, no reuse (optimal)

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);                              // for BOTH the skip and the break
    List<List<Integer>> result = new ArrayList<>();
    backtrack(candidates, 0, target, new ArrayList<>(), result);
    return result;
}

private void backtrack(int[] c, int start, int remaining,
                       List<Integer> path, List<List<Integer>> result) {
    if (remaining == 0) {                                 // exact hit
        result.add(new ArrayList<>(path));
        return;
    }

    for (int i = start; i < c.length; i++) {
        if (i > start && c[i] == c[i - 1]) continue;      // skip duplicate SIBLINGS
        if (c[i] > remaining) break;                      // sorted: later ones are bigger too

        path.add(c[i]);
        backtrack(c, i + 1, remaining - c[i], path, result);   // i+1 — used at most once
        path.remove(path.size() - 1);
    }
}

Trace — candidates = [1,1,2,5,6,7,10] (sorted), target = 8:

Result [[1,1,6], [1,2,5], [1,7], [2,6]] ✓

• Time O(2^n) worst case, heavily pruned in practice · Space O(target / min) depth

Counter-questions on this approach

⭐ "[1,1,6] uses 1 twice. Doesn't the skip forbid that?"

No, and this is the key distinction. The input has two separate 1s, at indices 0 and 1 after sorting, so using both is legitimate — they're different elements.

What the skip forbids is trying the same value twice at the same level, which would build two identical subtrees.

Concretely: at depth 1 with start = 1, the loop's i = 1 equals start, so the guard doesn't fire and the second 1 is taken — producing [1,1]. Back at depth 0 with start = 0, the loop reaches i = 1 where i > start holds, so it skips — avoiding a second path that would also produce [1,...].

The i > start guard draws exactly that line: sibling repeats are cut, path repeats are kept.

⭐ "Three modifications at once. Do they interfere?"

No, and it's worth saying why rather than just asserting it. They act on different things:

• i + 1 constrains which element can be chosen next
• the skip constrains which value can be tried at this level
• the break constrains which values are worth trying at all

The only coupling is that both the skip and the break require the array to be sorted, which one sort provides.

⭐ "Why does the break come after the skip and not before?"

Either order is correct, since they're independent tests on the same i. Putting the skip first means a duplicate is dismissed without a comparison against remaining, which is marginally cheaper.

What would be wrong is breaking on the duplicate condition — that would abandon the whole level, including larger values that are still viable.

"What stops remaining going negative?"

The break. A candidate greater than remaining is never added, so the recursion is only entered with remaining >= 0. The alternative is to allow it and guard with if (remaining < 0) return;, which works without sorting but does strictly more work.

"How deep can this go?"

target / min(candidates) = 30 / 1 = 30 levels. And since each element is used at most once, also bounded by n = 100. So 30.

"Does the result contain [1,1,6] only once even though there are two ways to pick the 1s?"

Yes — picking indices {0,1,4} is the only path the skip permits. Indices {1,0,4} isn't reachable because the loop only moves forward, and there's no third 1 to offer an alternative. That's the deduplication working by construction.

Comparison

4. Why the Optimal Wins

Both are correct. The difference is that the Set version explores every duplicate subtree to completion and then discards the results — and with heavy duplication that ratio gets very bad. [1,1,1,1,1] with target 3 produces [1,1,1] ten times; the pruned version generates it once.

The deeper point is compositional: three independent constraints, each a single line, none aware of the others. That's the payoff for establishing the template cleanly in question 1.

The framing worth keeping:

Sort once; it enables both the duplicate skip and the sorted break. Then i + 1 forbids reusing an element, and i > start forbids re-trying a value as a sibling — two different rules that don't conflict.

5. Java Prerequisites

The three rules together

Arrays.sort(candidates);                            // serves both the skip and the break

for (int i = start; i < c.length; i++) {
    if (i > start && c[i] == c[i-1]) continue;      // duplicate sibling
    if (c[i] > remaining) break;                    // sorted: later ones are bigger
    path.add(c[i]);
    backtrack(c, i + 1, remaining - c[i], ...);     // i+1: no reuse
    path.remove(path.size() - 1);
}

continue vs break — continue skips this candidate; break abandons the rest of the level. Using break for the duplicate check would be a bug: it would discard larger, still-viable values.

LinkedHashSet preserves insertion order, unlike HashSet — useful if deterministic output order matters.

6. Interview Communication Guide

Clarifying questions: Can candidates repeat (yes)? Can a single element be used twice (no — but two equal elements at different indices can both be used)? Are all candidates positive (yes — it licenses the break)? Does order within a combination matter (no)?

The pitch

"This is the three previous questions composed together, and the nice thing is that the rules are independent.

From Subsets: pass i + 1, so each element is used at most once.

From Subsets II: sort, then skip a value that repeats its predecessor at the same level — if (i > start && c[i] == c[i-1]) continue;.

From Combination Sum: since the array is sorted and all candidates are positive, break as soon as a candidate exceeds the remaining target, because everything after it is larger too.

The one sort serves both the skip and the break.

The distinction worth being precise about is that [1,1,6] is a valid answer even though 1 appears twice — the input has two separate 1s, so using both is legitimate. What's forbidden is trying the same value twice at the same level, which would build two identical subtrees.

The i > start guard draws exactly that line. At depth 1 with start = 1, i = 1 equals start, so the second 1 is allowed and I get [1,1]. Back at depth 0 with start = 0, reaching i = 1 means i > start, so it's skipped. Sibling repeats cut, path repeats kept.

The three rules don't interfere because they constrain different things: i + 1 constrains which element comes next, the skip constrains which value is tried at this level, the break constrains which are worth trying at all."

Edge cases to volunteer:

Name [1,1] with both targets. Target 2 must yield [1,1] (proving path repeats are allowed); target 1 must yield a single [1] (proving sibling repeats are cut). Together they pin down the guard exactly.

7. Follow-Up Questions — Modified Constraints

⭐ "What if a candidate could be zero?"

The break still works, but a zero contributes nothing and can be picked at most once here (thanks to i + 1), so it just produces duplicate-valued combinations like [0,5] alongside [5]. Whether those count as distinct depends on the problem's definition — worth asking rather than assuming. In Combination Sum I, where reuse is allowed, a zero would make the search non-terminating.

⭐ "Count the combinations rather than listing them."

This becomes 0/1 knapsack counting: dp[t] += dp[t - c], iterating targets descending so each item is used once. O(n · target) = 100 × 30 = 3,000 operations, versus an exponential search. The descending iteration is exactly what enforces "at most once" — the mirror of Combination Sum I's ascending loop.

"Use the counting formulation to deduplicate instead."

Group into (value, count) pairs and, for each distinct value, choose how many copies to take from 0 to count. No skip condition needed at all — each distinct multiset is generated once by construction. Cleaner when duplication is heavy.

"What if target were 10^4?"

Enumeration becomes hopeless — the number of combinations explodes — but the counting DP is O(n · target) = 10^6, still fine. Another case where counting and listing diverge sharply.

"Return combinations in sorted order."

Free — the sort makes each combination internally non-decreasing, and the DFS emits them in lexicographic order. Same bonus as in Combination Sum I.

"What if elements were objects with a weight, not plain integers?"

The skip needs an equality notion for "duplicate", and the sort needs a comparator by weight. If two objects have equal weight but differ in identity, you'd have to decide whether swapping them yields a distinct answer — which is a product question, not an algorithmic one, and worth surfacing rather than guessing.