LeetCode 39 · Backtracking

Combination Sum, explained with a picture

Filling a piggy bank with reusable coins.

MediumBacktracking
▶ Watch it step by step

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

  1. 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.
  2. Pass a start index. dfs(start, left, path) loops for i in range(start, len(coins)).
  3. Allow reuse by not moving on. After choosing coins[i], recurse with i, not i + 1. The same coin is available again.
  4. Stop on exact or over. If left == 0 save a copy of the path. Because the coins are sorted, once coins[i] > left, every later coin is also too big, so break.
  5. 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 res

In 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

ApproachTimeSpace
Brute force (all orderings)Exponential in target / smallest coin, and larger because of the orderingsO(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 prunesO(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 + 1 instead of i. 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 break on an unsorted list. A big coin early on would hide smaller ones that follow.
  • Saving path itself, not a copy, when the path is shared and mutated.
Your turn: each coin at most twice

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.

Check what stuck

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?

2. Why can the shown code break as soon as coins[i] > left?

3. A learner changes dfs(i, ...) to dfs(i + 1, ...). Which input still returns the right answer?

Score 60% or more and the lesson is marked complete.