LeetCode 40 – Combination Sum II

Combination Sum II is Combination Sum with two changes: each candidate may be used only once, and the input can contain duplicates. The first change is one character. The second is one line — and that line, i > start rather than i > 0, is the single most misunderstood condition in the whole backtracking family.

The problem

Given positive candidates that may repeat and a target, find every unique combination summing to the target. Each element of the array may be used at most once — but if a value appears twice in the input, it may appear twice in a combination.

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]]

[1,1,6] is legal — there really are two 1s in the input.
[1,7] must appear ONCE, even though either 1 could have produced it.

That last line is the whole difficulty. Two identical values at different indices are different array elements but produce identical combinations, and only one may be reported.

Sorting is now mandatory

In Combination Sum, sorting was an optimisation. Here it is a correctness requirement: the de-duplication works by comparing each candidate to its immediate predecessor, which only identifies duplicates if equal values are adjacent. Sort first or the skip below silently misses cases.

i > start, not i > 0

The rule to implement is: at any one level of the recursion, do not try the same value twice. Picking the first 1 and picking the second 1 as the opening move lead to identical subtrees, so the second is pure duplication.

But picking 1 and then picking another 1 one level deeper is completely legitimate — that is how [1,1,6] gets found. The skip has to distinguish "the same value again at this level" from "the same value again at the next level down", and the index the recursion started at is exactly what separates them:

if (i > start && candidates[i] == candidates[i - 1]) continue;

i == start is the first candidate this level is allowed to consider — always take it, even if it equals its predecessor, because that predecessor belongs to a shallower level and was a genuinely different pick. Every later i at the same level that repeats its neighbour is the duplicate to skip.

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

level 0, start = 0:  i=0 take 1        i=1 SKIP (i > start, same as i-1)
                       |
level 1, start = 1:    i=1 take 1  ←  allowed: i == start
                         |
level 2, start = 2:      ... 6 completes [1, 1, 6]

Write i > 0 instead and the i=1 pick at level 1 is skipped too:
[1,1,6] is never found.

That is the failure mode to remember. i > 0 does not produce duplicates — it produces missing answers, which is much harder to notice, because the output still looks plausible.

Java

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);      // required: the skip below compares neighbours
        backtrack(result, new ArrayList<>(), candidates, 0, target);
        return result;
    }

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

        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) break;    // sorted: the rest are bigger too

            // Same value already tried at THIS level. i > start, not i > 0.
            if (i > start && candidates[i] == candidates[i - 1]) continue;

            path.add(candidates[i]);
            // i + 1: each array element may be used at most once.
            backtrack(result, path, candidates, i + 1, remaining - candidates[i]);
            path.remove(path.size() - 1);            // undo
        }
    }
}

Python

class Solution:
    def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates.sort()               # required, not an optimisation
        result = []
        path = []

        def backtrack(start: int, remaining: int) -> None:
            if remaining == 0:
                result.append(path[:])
                return

            for i in range(start, len(candidates)):
                if candidates[i] > remaining:
                    break
                if i > start and candidates[i] == candidates[i - 1]:
                    continue            # same value already tried at this level

                path.append(candidates[i])
                backtrack(i + 1, remaining - candidates[i])   # i + 1: use each once
                path.pop()

        backtrack(0, target)
        return result

The two changes, side by side

Being able to draw this table is a better answer than either solution on its own. It shows the two problems are one template with a parameter, which is the thing worth carrying into the next backtracking question.

Why not de-duplicate at the end

Collecting everything and pushing it through a Set is correct and it is the wrong answer. It does the exponential work anyway and then pays again to discard most of it, and it needs a canonical form for each combination — a sorted copy — to make the set comparisons meaningful. Pruning at the point of choice never generates the duplicate at all. Say that trade-off out loud if you reach for the set first.

Complexity

O(2n · k) where k is the average combination length. Each element is either in or out of a combination, giving at most C(n,0) + C(n,1) + … + C(n,n) = 2n subsets to consider, and copying each successful path costs O(k). Space is O(n) for the recursion depth and the path, not counting the output.

The pruning does not change that bound and does change the runtime enormously on real input — worth stating as two separate facts rather than conflating them.

What the interviewer is checking

• i > start. This is the question. i > 0 loses valid answers, and losing answers is worse than duplicating them.
• That the recursion advances to i + 1.
• That you sort, and know it is now required rather than an optimisation.
• [1,1,6] from [10,1,2,7,6,1,5] — the case that separates the two conditions.
• That you prune at the point of choice instead of de-duplicating at the end.
• That you can articulate exactly what changed from problem 39.