Combination Sum

Posted on

Given a list of distinct positive integers (candidates) and a target, return every unique combination whose numbers sum to the target. Each candidate may be used unlimited times, and two combinations are the same if they contain the same numbers regardless of order.

Example#

For candidates = [2, 3, 6, 7] and target = 7, the combinations are [2, 2, 3] and [7]. For candidates = [2, 3, 5] and target = 8, the answer is [2, 2, 2, 2], [2, 3, 3], and [3, 5].

Brute force note#

Generating all sequences and filtering those that sum to the target produces duplicates like [2, 3, 2] and [3, 2, 2] and wastes effort on sums that already overshoot the target.

Optimal approach#

Backtrack while enforcing non-decreasing choices to avoid permutation duplicates. Track a start index: at each step you may reuse the current candidate (so pass the same index) or move forward to later candidates, but never go backward. Subtract the chosen value from the remaining target. When the remainder hits zero, record the path; if it goes negative, prune.

 1def combination_sum(candidates, target):
 2    result = []
 3    candidates.sort()
 4
 5    def backtrack(start, remaining, path):
 6        if remaining == 0:
 7            result.append(path[:])
 8            return
 9        for i in range(start, len(candidates)):
10            if candidates[i] > remaining:
11                break  # sorted, so all later are too big
12            path.append(candidates[i])
13            backtrack(i, remaining - candidates[i], path)  # i, reuse allowed
14            path.pop()
15
16    backtrack(0, target, [])
17    return result
18
19
20print(combination_sum([2, 3, 6, 7], 7))  # [[2, 2, 3], [7]]
21print(combination_sum([2, 3, 5], 8))     # [[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Complexity#

Time is exponential in the worst case, roughly O(candidates raised to (target / smallest candidate)), because the search tree branches on every reusable candidate. Space is O(target / smallest candidate) for the recursion depth and path.

This is a core backtracking problem: choose, recurse, undo. Reinforce the pattern there, then continue through the 60-day curriculum.