DSA Combination Sum

The problem

Combination Sum asks which groups of candidate numbers add up to a target. The candidates are distinct positive numbers. One candidate may be used many times inside a group.

The order inside a group makes no new group. The group [2, 3] and the group [3, 2] are the same answer. This article writes each group in rising order, and each group appears once.

cases = [
    ([2, 3, 6, 7], 7, [[2, 2, 3], [7]]),
    ([2, 3, 5], 8, [[2, 2, 2, 2], [2, 3, 3], [3, 5]]),
    ([2, 3], 6, [[2, 2, 2], [3, 3]]),
    ([2], 1, []),
]
for candidates, target, expected in cases:
    print("candidates", candidates, "target", target, "groups:", expected)

Read the last row with care. It has no group at all. Every pick adds at least 2, so a target of 1 is out of reach from the first step.

Intuition: the greedy pick can block every completion

A greedy choice takes the best-looking option now and never reconsiders it. Here, greedy means taking the largest candidate that still fits, again and again.

Greedy fails on a small case. With candidates [3, 4] and target 6, greedy takes 4 first. The remainder is 2, and no candidate fits it, so greedy stops one step from done. The group [3, 3] was there all along.

def greedy(candidates, target):
    path = []
    remaining = target
    for value in sorted(candidates, reverse=True):
        while value <= remaining:
            path.append(value)
            remaining -= value
    return path, remaining

path, remaining = greedy([3, 4], 6)
print("greedy path:", path)
print("remainder stuck at:", remaining)
print("target reached:", remaining == 0)

The miss is not bad luck. One early pick can block every completion of the group. The search must be able to undo a pick and try the next candidate instead.

Brute force: any candidate at any step, duplicates removed later

The brute force places one candidate at a time, in any order. It stops a branch when the running total hits the target or passes it. A counter records the search calls.

A set stores each distinct item once. Finished groups are stored as sorted tuples in a set, so the same group found in different orders collapses to one entry. The set hides the repeated work, but the call counter still shows it.

def combination_sum_brute(candidates, target):
    found = set()
    calls = [0]
    def search(path, total):
        calls[0] += 1
        if total == target:
            found.add(tuple(sorted(path)))
            return
        if total > target:
            return
        for value in candidates:
            path.append(value)
            search(path, total + value)
            path.pop()
    search([], 0)
    return sorted(list(group) for group in found), calls[0]

result, calls = combination_sum_brute([2, 3, 6, 7], 7)
for row in result:
    print(row)
print("groups:", len(result))
print("search calls:", calls)

The group [2, 2, 3] alone is found in three different orders. Each order costs its own branch of the search. The optimal solution removes the swapped copies by construction, not by cleanup afterwards.

The optimal solution: sorted candidates, a start index, and a hard cut

The state is the path, a start index, and the remaining target, and the search picks only candidates at or after the start index, so groups grow in rising order and no group is ever built twice. That one sentence is the core method.

Sorting adds a cut. When a candidate exceeds the remaining target, every later candidate is at least as large, so the loop breaks at once. Picking a candidate restarts the search at its own index, which is exactly what allows one candidate to be reused.

def combination_sum(candidates, target):
    candidates = sorted(candidates)
    results = []
    path = []
    pruned = [0]
    def search(start, remaining):
        if remaining == 0:
            results.append(list(path))
            return
        for i in range(start, len(candidates)):
            value = candidates[i]
            if value > remaining:
                pruned[0] += 1
                break
            path.append(value)
            search(i, remaining - value)
            path.pop()
    search(0, target)
    return results, pruned[0]

cases = [
    ([2, 3, 6, 7], 7, [[2, 2, 3], [7]]),
    ([2, 3, 5], 8, [[2, 2, 2, 2], [2, 3, 3], [3, 5]]),
    ([2, 3], 6, [[2, 2, 2], [3, 3]]),
    ([2], 1, []),
]
for candidates, target, expected in cases:
    result, pruned = combination_sum(candidates, target)
    print("target", target, "->", result, "match:", result == expected, "- pruned:", pruned)

All four cases match. The pruned counter rises each time the cut ends a loop early. The next sections put that counter next to the brute force call count, where the saving is plain to see.

Walkthrough: target 7 with candidates [2, 3, 6, 7]

The walk prints the path and the remaining target after each pick. A record line marks a finished group. A cut line marks a candidate that exceeded the remainder and ended its loop.

candidates = [2, 3, 6, 7]
target = 7
path = []
def search(start, remaining):
    if remaining == 0:
        print("record group:", list(path))
        return
    for i in range(start, len(candidates)):
        value = candidates[i]
        if value > remaining:
            print("cut at", value, "- remaining is", remaining)
            break
        path.append(value)
        print("pick", value, "- path:", list(path), "- remaining:", remaining - value)
        search(i, remaining - value)
        path.pop()
search(0, target)

Read the answer off the record lines. The groups [2, 2, 3] and [7] appear exactly once each. No swapped copy of either group appears anywhere in the walk.

Complexity

Worst-case time is exponential in the length of the longest possible group, which is the target divided by the smallest candidate. Pruning cuts branches early, but it does not change that worst case. No tidy closed formula exists, because the tree size depends on the actual candidate values.

Extra space is O(length of the longest group) besides the stored results. The path never holds more picks than one group under construction.

def brute_calls(candidates, target):
    calls = [0]
    def search(total):
        calls[0] += 1
        if total == target or total > target:
            return
        for value in candidates:
            search(total + value)
    search(0)
    return calls[0]

def optimal_calls(candidates, target):
    candidates = sorted(candidates)
    calls = [0]
    def search(start, remaining):
        calls[0] += 1
        if remaining == 0:
            return
        for i in range(start, len(candidates)):
            value = candidates[i]
            if value > remaining:
                break
            search(i, remaining - value)
    search(0, target)
    return calls[0]

for target in (7, 12):
    print("target", target, "- brute calls:", brute_calls([2, 3, 6, 7], target), "- optimal calls:", optimal_calls([2, 3, 6, 7], target))

The optimal search visits far fewer nodes at both targets. The start index removes the swapped duplicates, and the cut removes the overshoot branches before they grow.

Edge cases and pitfalls

A target of zero is reached by picking nothing. The empty group is the correct answer there, not a bug. A target below every candidate has no group, and the cut proves it in one step.

The candidates must be distinct. A repeated candidate breaks that promise, and the same group can then be built through either copy. The last rows of the block show the damage.

def combination_sum(candidates, target):
    candidates = sorted(candidates)
    results = []
    path = []
    pruned = [0]
    def search(start, remaining):
        if remaining == 0:
            results.append(list(path))
            return
        for i in range(start, len(candidates)):
            value = candidates[i]
            if value > remaining:
                pruned[0] += 1
                break
            path.append(value)
            search(i, remaining - value)
            path.pop()
    search(0, target)
    return results, pruned[0]

print("target 0:", combination_sum([2, 3], 0)[0])
print("no group exists:", combination_sum([2], 1)[0])
print("all candidates too big:", combination_sum([5, 6], 3)[0])
print("one candidate, used three times:", combination_sum([3], 9)[0])
print("repeated candidate input:", combination_sum([2, 2, 3], 4)[0])

The repeated row prints [2, 2] twice. Sorting cannot rescue that input, because the two copies are genuinely different positions with the same value. Distinct candidates are part of the problem statement.