The problem
Given distinct coin values and a target, list every combination of coins that adds up to the target. Each coin value may be used any number of times; order inside a combination doesn’t matter.
Input: coins = [2, 3, 6, 7], target = 7 Output: [[2, 2, 3], [7]]
Picture it
Picture filling a piggy bank to exactly the target. At each step you pick a coin to drop in, but only coins of the same value or later in the list (so [2,3] and [3,2] aren’t counted twice). If the total goes over, that branch is abandoned; if it hits the target exactly, that handful is an answer.
How to recognise it
- You must list every combination of numbers that hits an exact total, not just say whether one exists.
- Each number can be used again and again, so a combination can be long (many 2s) and its length is not fixed.
- Order inside a combination does not matter:
[2, 2, 3]and[3, 2, 2]are the same answer. - The limits are small (target at most 40, at most 30 distinct values, fewer than 150 answers), the sign of a search that is allowed to be exponential.
- A running total that can go over the target lets you cut a branch the moment it is hopeless. That combination of enumeration plus early stopping is backtracking: extend a partial answer, recurse, undo.
Start with brute force
Try every sequence: at each step add any coin that still fits, and when the total hits the target save it. To avoid listing the same combination in several orders, sort it and keep it in a set.
def combination_sum_brute(coins, target):
found = set()
def dfs(left, path):
if left == 0:
found.add(tuple(sorted(path)))
return
for c in coins:
if c <= left:
dfs(left - c, path + [c])
dfs(target, [])
return [list(t) for t in found]
It is correct, but it generates every ordering of every answer. For coins [2, 3, 6, 7] there are about 750,000 ordered sequences that reach 40, and at target 25 it makes about 9,900 calls. The combinations are far fewer, so most of the work is the same answer in a different order.
From brute force to the idea
- Kill the reorderings. Sort the coins. Let each step choose only a coin at the same or a later position than the previous one. Then
[2, 3]can be built but[3, 2]cannot. - Pass a start index.
dfs(start, left, path)loopsfor i in range(start, len(coins)). - Allow reuse by not moving on. After choosing
coins[i], recurse withi, noti + 1. The same coin is available again. - Stop on exact or over. If
left == 0save a copy of the path. Because the coins are sorted, oncecoins[i] > left, every later coin is also too big, sobreak. - Build the path with
path + [coin]. Each call gets its own list, so there is nothing to undo.
This is the key idea: a start index prevents reorderings, and recursing with the same index allows reuse. On the same input the shown code makes about 224 calls at target 25, and 973 at target 40.
The key idea
Backtracking with a start index (to avoid reorderings) and reuse allowed: recurse with the same index after choosing a coin.
Python solution
def combination_sum(coins, target):
coins.sort(); res = []
def dfs(start, left, path):
if left == 0:
res.append(path[:]); return
for i in range(start, len(coins)):
if coins[i] > left:
break # too big, and so is everything after
dfs(i, left - coins[i], path + [coins[i]]) # same coin may repeat
dfs(0, target, [])
return resIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (all orderings) | Exponential in target / smallest coin, and larger because of the orderings | O(answers + depth) for the set and recursion |
| Sorted start index (shown code) | Exponential in the worst case, about O(n^(T/m)) for n coins, target T and smallest coin m, but each combination appears once and break prunes | O(T / m) recursion depth and path, plus the output |
Edge cases
- No combination (
[5], target 3): returns[]. - Coin equal to the target (
[8], target 8): returns[[8]]. - Example (
[2, 3, 6, 7], target 7): returns[[2, 2, 3], [7]]. - Many reuses (
[2, 3], target 10 includes[2, 2, 2, 2, 2]): the recursion depth is up to target / smallest coin, which is at most 20 for target 40. - Target 0: returns
[[]], the empty combination. - Input order: coins can be given unsorted, but
coins.sort()sorts the caller's list in place. Pass a copy if the original order matters. - Distinct coins are assumed; the code does not remove duplicate values.
Common mistakes
- Recursing with
i + 1instead ofi. The coin can then be used only once:[2, 3, 6, 7]with target 7 returns[[7]]and misses[2, 2, 3]. - Looping from 0 every time instead of from
start. This gives[2, 2, 3],[2, 3, 2]and[3, 2, 2]as separate answers. - Using
breakon an unsorted list. A big coin early on would hide smaller ones that follow. - Saving
pathitself, not a copy, when the path is shared and mutated.
Same problem, but each coin value may be used at most twice. Describe how the recursion changes, then write it if you like.
Compare with our answer
Each coin now has three options: used zero, one or two times. Recurse per coin position (not per slot) and try each count, so reuse is bounded and orderings are still impossible.
def combination_sum_twice(coins, target):
coins = sorted(coins)
res = []
def dfs(i, left, path):
if left == 0:
res.append(path)
return
if i == len(coins):
return
for times in range(3): # use coin i 0, 1 or 2 times
if times * coins[i] > left:
break
dfs(i + 1, left - times * coins[i], path + [coins[i]] * times)
dfs(0, target, [])
return res
combination_sum_twice([2, 3, 6, 7], 7) returns [[7], [2, 2, 3]]. Worst case time is O(3^n) for n coins, and space is O(n) beyond the output.
A strong answer mentions: choosing a count per coin with a cap of two, moving to the next position afterwards, and that this is still free of duplicate combinations.
1. A vending machine must list every set of coins (any number of each denomination) that makes exactly 90 cents, ignoring order. Which approach fits best?
The task is to list the combinations, not to count them, so each combination has to be generated. A start index stops reorderings and recursing with the same index allows repeats. Greedy gives one answer, and counting does not list them.
2. Why can the shown code break as soon as coins[i] > left?
After the sort, coins only grow with i, so if one coin does not fit, none of the rest will. That is why the code also has to sort first.
3. A learner changes dfs(i, ...) to dfs(i + 1, ...). Which input still returns the right answer?
With i + 1 each coin is used at most once. Only [8] needs a single coin: [8]. The other inputs return [[7]], [[3, 5]] and [], missing combinations that reuse a coin.
Score 60% or more and the lesson is marked complete.