Combination Sum (LeetCode 39)

The problem

You get a list of distinct positive integers candidates and a target. Return every unique combination of candidates whose sum is exactly target. Each candidate may be used any number of times. Two combinations are the same if they use the same numbers the same number of times, in any order.

Input:  candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]

2 + 2 + 3 = 7 and 7 = 7. [2, 3, 2] is the same combination as [2, 2, 3], so it isn’t listed again.

How to think about it

Start with brute force. Try every sequence of candidates until the running sum reaches or passes the target, and keep the ones that hit it exactly. That explores every ordering, so [2,2,3], [2,3,2] and [3,2,2] are all found and you have to de-duplicate. The tree is enormous.

Fix the duplicates with a start index. As in Subsets, only allow picks at index start or later, so each combination is built in non-decreasing order and has one path. The twist: since a number can be reused, the recursive call passes i, not i + 1. You may pick the same candidate again, but never go back to an earlier one.

The key insight for speed: sort, then break on overshoot. Track rem, the amount still needed. If candidates[i] > rem, adding it can’t work, and because the list is sorted, every later candidate is even bigger. So you don’t continue, you break out of the loop. That one line prunes whole sub-trees.

Which pattern is this? Backtracking with pruning. The tell is “find all combinations that sum to a target”. The state you carry is (start, path, rem), and rem == 0 is the success condition.

Approach

1. Sort candidates.
2. bt(start, path, rem): if rem == 0, record a copy of path and return.
3. For i from start onward: if candidates[i] > rem, break.
4. Otherwise append it, recurse with bt(i, path, rem - candidates[i]) (same i, reuse allowed), then pop.
5. Call bt(0, [], target).

Solution

def combination_sum(candidates, target):
    res = []; candidates.sort()               # sorted, so we can break early
    def bt(start, path, rem):
        if rem == 0: res.append(path[:]); return
        for i in range(start, len(candidates)):
            if candidates[i] > rem: break    # this and every later candidate overshoots
            path.append(candidates[i]); bt(i, path, rem - candidates[i]); path.pop()   # i: reuse allowed
    bt(0, [], target); return res
# combination_sum([2,3,6,7], 7) -> [[2,2,3],[7]]

Dry run

On candidates = [2, 3, 6, 7], target = 7:

Every dead end stops at the first candidate that’s too big. Two combinations are found.

Complexity

• Time: exponential. A loose bound is O(n^(T/m)), where T is the target and m the smallest candidate, since the tree is at most T/m deep with up to n branches per node. Pruning makes it much faster in practice.
• Space: O(T/m) for the recursion depth and path, since every pick is at least m.

Edge cases and pitfalls

• Recursing with i + 1 forbids reuse: you’d miss [2, 2, 3]. That’s Combination Sum II’s rule.
• Recursing with 0 instead of i lets you go back to smaller numbers and produces [2,3,2], [3,2,2] as duplicates.
• Using continue instead of break is still correct but loses the pruning. And break is only safe because you sorted.
• No combination exists (e.g. [2], target 3) returns [].
• Candidates are positive. With zero or negatives, the recursion would never terminate.

Related problems

• Combination Sum II (LeetCode 40): each number used at most once, with duplicates in the input.
• Coin Change II (LeetCode 518): the same question but only the count of combinations, solved with DP.
• Combinations (LeetCode 77): the same start index, with a fixed size instead of a target.