Combination Sum II (LeetCode 40)

The problem

You get a list of positive integers candidates, which may contain duplicates, and a target. Return every unique combination that sums to target, where each element of the list can be used at most once. No combination may appear twice in the output.

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

There are two 1s, so [1, 7] could be built with either one. It still counts once. [1, 1, 6] uses both 1s, which is allowed.

How to think about it

Start with brute force. Generate every subset (2ⁿ), keep those that sum to the target, and de-duplicate with a set of sorted tuples. That’s correct but slow, and the de-dup is a patch over the real problem.

Two rules you already know, combined. From Combination Sum: carry the remaining target rem, sort, and break as soon as a candidate exceeds rem. From Subsets: each element is used at most once, so recurse with i + 1. Neither rule alone stops duplicates caused by repeated values.

The key insight: skip a repeated value at the same level. After sorting, the list is [1, 1, 2, 5, 6, 7, 10]. At the root, the loop tries “first pick is the first 1”, and later “first pick is the second 1”. The second branch can only find combinations the first already found. So inside one loop, if i > start and candidates[i] == candidates[i-1], skip. This is exactly the Subsets II rule. Picking the second 1 in a deeper call (after the first 1) is still allowed, which is how [1, 1, 6] is found.

Which pattern is this? Backtracking with pruning and de-duplication. The tell is “sum to target”, “each number once”, and “the input has duplicates but the output must not”.

Approach

1. Sort candidates.
2. bt(start, path, rem): if rem == 0, record a copy and return.
3. Loop i from start. If i > start and the value equals the previous one, continue.
4. If candidates[i] > rem, break: everything after is bigger.
5. Otherwise append, recurse with bt(i + 1, path, rem - candidates[i]), pop.

Solution

def combination_sum2(candidates, target):
    res = []; candidates.sort()
    def bt(start, path, rem):
        if rem == 0: res.append(path[:]); return
        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i-1]: continue   # same value, same level
            if candidates[i] > rem: break                                  # sorted: rest overshoot too
            path.append(candidates[i]); bt(i + 1, path, rem - candidates[i]); path.pop()   # i+1: use once
    bt(0, [], target); return res
# combination_sum2([10,1,2,7,6,1,5], 8) -> [[1,1,6],[1,2,5],[1,7],[2,6]]

Dry run

Sorted input: [1, 1, 2, 5, 6, 7, 10], target = 8.

The single skip at the root removes the whole duplicate sub-tree that would have repeated [1, 2, 5] and [1, 7].

Complexity

• Time: O(2ⁿ · n) in the worst case: at most every subset is explored, with O(n) to copy a match. Sorting and the break prune much of that.
• Space: O(n) for the recursion depth and path, since each element is used at most once.

Edge cases and pitfalls

• Order of the two checks. The duplicate check and the break can go in either order here, but both must come before the append.
• i > 0 instead of i > start wrongly forbids [1, 1, 6].
• Recursing with i (as in Combination Sum) reuses the same element and gives [1, 1, 1, …] style wrong answers.
• No valid combination returns []. Target smaller than every candidate breaks immediately at the root.
• The code sorts the input in place.

Related problems

• Combination Sum (LeetCode 39): unlimited reuse, distinct candidates.
• Subsets II (LeetCode 90): where the same-level skip rule comes from.
• Partition to K Equal Sum Subsets (LeetCode 698): backtracking to hit a target sum several times over.