Combination sum

Lesson 11.4 · Medium · Prune early · 10 min · by Vinay C

We'll cover the following

Overview
Watch it run
The idea
Complexity
In Python
Summary

Pick numbers (each can be reused) that add up to the target. List every distinct combination.

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

add20

Add 2. Sum is 2 of 12. Try to reuse numbers from here on.

path [2] · found 0

1 / 57

The idea

Complexity

Time	Space	Why
`Exponential in target / smallest coin`	`O(target / smallest)`	Sorting lets the loop stop at the first candidate that overshoots.

In Python

def combination_sum(cands, target):
    cands.sort(); res, path = [], []
    def dfs(start, total):
        if total == target: res.append(path[:]); return
        for i in range(start, len(cands)):
            if total + cands[i] > target: break      # prune
            path.append(cands[i])
            dfs(i, total + cands[i])                 # i: allow reuse
            path.pop()
    dfs(0, 0)
    return res

</> Now code it →Try it on LeetCode: Combination Sum →

Summary: say it in the interview

Add a number, recurse, then remove it. Keeping candidates sorted lets you prune: once adding a number overshoots the target, every later number would too, so you can stop that whole branch.
Time Exponential in target / smallest coin, space O(target / smallest). Sorting lets the loop stop at the first candidate that overshoots.