Combination Sum II

Combination Sum II is the classic "backtracking with duplicates" problem. It teaches the single most reusable move for combination search: sort first, then skip duplicate siblings so the same combination is never generated twice.

The slow way first

The obvious idea: generate every subset, keep the ones that sum to the target, then throw the duplicates into a set to de-duplicate. That works, but it explores 2^n subsets and wastes huge effort building combinations we will only delete later. The de-dup-with-a-set fix is a band-aid over a tree we should never have grown.

The question to ask: can I avoid creating the duplicate combinations in the first place? If I do, I never pay to detect and discard them.

The idea

Sort the candidates so equal numbers sit next to each other. Then backtrack: at each step choose one number, subtract it from the remaining target, and recurse forward (the start index moves right so no element is reused). The de-dup trick is one line: at a given level, skip a candidate equal to its left sibling that we already tried. Picking the first copy already explored every combination that starts with that value, so a second copy would only repeat them.

Two more prunes fall out of the sort for free: if nums[i] > remaining, every later candidate is also too big, so we break the loop; and a candidate equal to its left sibling is skipped with continue.

Walk through it

Step through the animation on [1, 1, 2, 5, 6, 7, 10] (the sorted input) with target 8. Each node shows the remaining target. We descend 8 → 7 → 6 → 0 by picking 1, the second 1, then 6 — that reaches 0, so [1, 1, 6] is recorded. We then backtrack to the root, where the next candidate is another 1 at the same level. Because it equals the sibling we already tried, we skip it — that one check is what keeps [1, 1, 6] from being generated a second time.

Pseudocode

sort candidates
result = []
backtrack(start, remaining, combo):
    if remaining == 0:
        record a copy of combo
        return
    for i from start to end:
        if i > start and nums[i] == nums[i - 1]:
            continue                 # skip duplicate sibling
        if nums[i] > remaining:
            break                    # sorted: the rest are too big
        choose nums[i]; recurse(i + 1, remaining - nums[i]); un-choose
backtrack(0, target, [])

The Python solution

def combination_sum2(nums, target):
    nums.sort()
    res, combo = [], []
    def backtrack(start, remaining):
        if remaining == 0:
            res.append(combo[:])
            return
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue
            if nums[i] > remaining:
                break
            combo.append(nums[i])
            backtrack(i + 1, remaining - nums[i])
            combo.pop()
    backtrack(0, target)
    return res

• nums.sort() groups equal values, enabling both the duplicate skip and the break prune.
• The base case remaining == 0 records combo[:] — a copy, because combo keeps mutating.
• i > start and nums[i] == nums[i - 1] is the heart of it: skip a value equal to the one we already tried at this level. The i > start guard means we still allow the first copy.
• nums[i] > remaining then break cuts the whole tail of the loop, since the array is sorted.
• We recurse with i + 1 (not i), so each element is used at most once, then combo.pop() undoes the choice before trying the next sibling.

Complexity

The worst case is still exponential — that is inherent to listing combinations — but sorting plus the two prunes cut the tree dramatically, and we never generate a duplicate to throw away. The extra space is O(n) for the recursion depth and the working combo.

When this pattern shows up

Practice