4.18.5 — Combination Sum II

LeetCode 40 · Medium

The problem

Find every unique combination summing to the target. Each number in the input may be used at most once, and the input may contain duplicates.

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

→ [[1,1,6], [1,2,5], [1,7], [2,6]]

[1,1,6] uses both 1s, which is legal because there are two of them. But [1,7] appears only once, even though either 1 could have formed it.

The pattern

This is 4.18.2 Combination Sum and 4.18.4 Subsets II combined, with two changes from Combination Sum:

change	reason
backtrack(i + 1, ...) instead of i	each element used at most once
the sorted duplicate skip	the input has repeats

Neither is new. What makes this problem worth doing is that the two rules look like they contradict each other and do not.

The rule that looks contradictory

[1,1,6] is a valid answer. So two 1s can appear in the same combination. But the duplicate skip says do not use the same value twice.

Both are true, because they are talking about different things:

• Two 1s in the same combination is a value used at two different depths of the tree — one 1 is the parent choice, the other is a child choice. Allowed, and that is what i + 1 supports: the second 1 is a different array element.
• Two 1s as different first choices is a value tried twice among siblings — same depth, same position. That produces the identical subtree twice. Forbidden.

The guard i > start separates them precisely, because i == start is the first choice at this level, which may legitimately equal the parent's value.

This is the same reasoning as 4.18.4, and if it did not fully land there, this problem is where it should.

The solution

Python

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        result = []
        path = []

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

            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i - 1]:
                    continue                          # sibling duplicate
                if candidates[i] > remaining:
                    break                             # sorted → all later ones too big

                path.append(candidates[i])
                backtrack(i + 1, remaining - candidates[i])   # i + 1: no reuse
                path.pop()

        backtrack(0, target)
        return result

TypeScript

function combinationSum2(candidates: number[], target: number): number[][] {
  candidates.sort((a, b) => a - b);
  const result: number[][] = [];
  const path: number[] = [];

  function backtrack(start: number, remaining: number): void {
    if (remaining === 0) {
      result.push([...path]);
      return;
    }
    for (let i = start; i < candidates.length; i++) {
      if (i > start && candidates[i] === candidates[i - 1]) continue;
      if (candidates[i] > remaining) break;

      path.push(candidates[i]);
      backtrack(i + 1, remaining - candidates[i]);
      path.pop();
    }
  }

  backtrack(0, target);
  return result;
}

The sort does two jobs. It makes equal values adjacent so the duplicate guard works, and it makes the break legal so one oversized candidate prunes all the rest.

Order of the two checks. The duplicate skip uses continue and must come before the break, because a skipped duplicate is not a reason to abandon the whole loop.

remaining == 0 is the only success case. Since all candidates are positive, overshooting is caught by the break and never reaches the base case as a negative.

Trace

[10,1,2,7,6,1,5] sorted is [1,1,2,5,6,7,10], target 8.

At start = 0, i = 0 (the first 1): allowed. Path [1], remaining 7, recurse from index 1.

• i = 1 (the second 1): i == start here (start is 1), so allowed. Path [1,1], remaining 6 → eventually reaches 6 and records [1,1,6] ✓.
• i = 2 (value 2): path [1,2], remaining 5 → picks up 5 → [1,2,5] ✓.
• i = 3 (value 5): remaining 2, and everything from here is larger → dead.
• i = 5 (value 7): remaining 0 → [1,7] ✓.

Back at start = 0, i = 1 (the second 1): now i > start and it equals candidates[0] → skipped. That is what prevents a second [1,7] and a second [1,2,5].

Then i = 2 (value 2): path [2], remaining 6 → [2,6] ✓.

Four unique combinations. ✓

Complexity

Bounded by O(2^n \times n) in the worst case — the number of subsets — though the sum constraint and the two prunings cut it far below that in practice.

O(n) space beyond the output.

The comparison worth memorising

problem	reuse	duplicates in input	recurse with	duplicate guard
Subsets	no	no	i + 1	none
Subsets II	no	yes	i + 1	i > start
Combination Sum	yes	no	i	none
Combination Sum II	no	yes	i + 1	i > start

Four problems, two independent switches. Once you see the table, they stop being four problems.

Where this goes next

• Palindrome Partitioning — the same start-index loop where the choice is where to cut rather than which element to take. 4.18.7.
• Combination Sum III — exactly k numbers from 1 to 9, so add a length check.
• Partition to K Equal Sum Subsets — much harder, and it needs both this template and memoisation over a bitmask of used elements.

What the interviewer will push on

"How can [1,1,6] be valid if you skip duplicates?" Depth versus siblings. This is the question the problem exists to ask, so have the sentence ready.

"Why i + 1 here but i in Combination Sum?" Reuse allowed or not.

"Why sort?" Two reasons: the duplicate guard needs adjacency, and the break needs order.

"Why continue for one check and break for the other?" A duplicate skips one branch; an oversized candidate kills every remaining branch.

One thing to volunteer: put the four-problem table on the whiteboard. It shows that you see a family with two switches rather than four separate memorised solutions, and that is exactly the transferable understanding being tested.

Next: 4.18.6 Word Search — backtracking on a grid, where the state being undone is the board itself.