Problem Statement

Combination Sum II

You are given a list of numbers (called candidates) and a target number. Your job is to find every group of numbers from the list that adds up exactly to the target. Two rules make this tricky. First, each number in the list can be used at most once, so if the number 1 appears twice in the list, you can use it twice, but you cannot reuse a single copy. Second, the answer must not contain duplicate groups. If you found [1,7] once, you should not list it again. The tool we use here is backtracking. Backtracking means we build a group one number at a time, and whenever the path stops working, we undo the last choice and try a different one. Think of it like exploring a maze: you walk down a hallway, and if it dead-ends, you back up to the last fork and take another turn. That fits this problem because we have to try many combinations, and we need a clean way to back out of bad ones and explore the rest.

mediumBacktrackingBacktrackingTime: O(2^n) · Space: O(n)

Signals to notice

combinations summing to target, each element used onceskip duplicate candidatessort first

Brute force first

Not applicable — enumeration with constraints.

The key insight

Sort. Backtrack from current index (no reuse). Skip candidates[i] when equal to candidates[i-1] at same level. O(2^n).

Trace it on `candidates=[10,1,2,7,6,1,5], target=8`

sort -> [1,1,2,5,6,7,10]; call backtrack(start=0, target=8, path=[])
i=0 pick 1 -> path=[1], target=7; recurse(start=1): pick 1 -> path=[1,1], target=6; recurse(start=2): pick 6 (skip 2,5) reaches target=0 -> record [1,1,6]
back at path=[1] (target=7), i=2 pick 2 -> path=[1,2], target=5; recurse(start=3): pick 5 -> target=0 -> record [1,2,5]
still path=[1], i=4 pick 7 -> target=0 -> record [1,7]; i=5 candidates[5]=7>... 7-? wait: path=[1] target=7, pick 7 gives 0 (already done); next i candidates>target break
back at top (target=8), i=1 is dup of i=0 at same level -> skip; i=2 pick 2 -> path=[2], target=6; recurse: pick 6 -> target=0 -> record [2,6]
continue top loop: i=3 pick 5 -> remaining 3, no candidate completes; i=4 pick 6 -> remaining 2, none; i=5 pick 7 -> remaining 1, none; i=6 candidates[6]=10>8 break
return result = [[1,1,6],[1,2,5],[1,7],[2,6]]

What must stay true

Sorting groups duplicates. Skipping same-value candidates at the same recursion level prevents duplicate combinations.

Shape of the loop

sort(candidates)
backtrack(start, target, path):
  if target == 0: record path; return
  for i in start..n-1:
    if candidates[i] > target: break        # pruned, rest larger
    if i > start and candidates[i] == candidates[i-1]: continue  # skip dup at level
    backtrack(i+1, target - candidates[i], path + candidates[i])

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not handling duplicates — [1,1,2] without skipping generates duplicate [1,2] combinations.

Backtracking Pattern