LeetCode 40 · Backtracking

Combination Sum II, explained with a picture

Each coin used once, no repeated handfuls.

MediumBacktracking
▶ Watch it step by step

The problem

Given coins (values may repeat) and a target, list every combination that adds up to the target, using each coin at most once, with no repeated combinations.

Input:  coins = [2, 5, 2, 1, 2], target = 5
Output: [[1, 2, 2], [5]]

Picture it

Picture a handful of coins on a table, some with the same value. Sort them. Each coin can go into the piggy bank once. At each level we skip a coin if it has the same value as the one just tried at that level (otherwise we’d form the same handful twice). Going over the target ends a branch early.

How to recognise it

  • You must list every combination that adds up to a target, as in Combination Sum, but now each coin can be used at most once.
  • The coins can repeat in value. Two 2s are different coins but give the same handful, and the answer must not list [1, 2, 2] twice.
  • Order inside a combination does not matter.
  • Up to 100 coins (values 1 to 50) and a target of at most 30. That is too many coins to try every subset, but the small target lets you stop branches early.
  • The recipe is backtracking with a start index, plus the sort and skip equal neighbours trick from Subsets II.

Start with brute force

Look at every subset of the coins, keep those whose sum equals the target, and remove repeated handfuls with a set.

from itertools import combinations

def combination_sum2_brute(coins, target):
    found = set()
    for r in range(len(coins) + 1):
        for chosen in combinations(coins, r):
            if sum(chosen) == target:
                found.add(tuple(sorted(chosen)))
    return [list(t) for t in found]

There are 2^n subsets. For 20 coins that is about a million subsets to test, and for 100 coins it is 2^100 (around 10^30), which can never finish. Space also grows with the set of found answers.

From brute force to the idea

  1. Sort the coins. Equal values become neighbours, and a coin bigger than what is left means all later coins are too big.
  2. Use a start index. dfs(start, left, path) tries coins[i] for i from start, so each combination is built in only one order.
  3. Use each coin once. After choosing coin i, recurse from i + 1.
  4. Skip repeats at the same level. If i > start and coins[i] == coins[i - 1], choosing it would rebuild the same handful that the earlier copy already built, so continue. A later copy is still available deeper, because start has moved on.
  5. Prune. If coins[i] > left, break. Because the list is sorted, nothing later can fit either. If left == 0, save a copy of the path.

This is the key idea: sort, move the start index forward, and skip an equal coin that is not the first choice at its level.

The key idea

Sort + backtracking moving to i + 1 (no reuse) + skip equal neighbours at the same level.

Python solution

def combination_sum2(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 i > start and coins[i] == coins[i - 1]:
                continue                  # same value at this level: skip
            if coins[i] > left:
                break
            dfs(i + 1, left - coins[i], path + [coins[i]])   # each coin once
    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 (every subset)O(n · 2^n): sum of each subset, plus sorting the matchesO(answers): the set of found handfuls
Sort, skip and prune (shown code)O(2^n) in the worst case, but break cuts every branch whose total is already too big, so with a target of at most 30 the tree is smallO(n) for the recursion and path, plus the output

Edge cases

  • Example ([2, 5, 2, 1, 2], target 5): returns [[1, 2, 2], [5]].
  • Duplicates that must be used together ([3, 3], target 6): returns [[3, 3]].
  • No answer ([2], target 1): returns [].
  • Distinct coins ([10, 1, 2, 7, 6, 1, 5], target 8): returns [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]].
  • A single coin that is exactly the target ([1, 1], target 1): returns [[1]], once, not twice.
  • Input is changed: coins.sort() sorts the caller's list in place.
  • Performance: 100 coins with many repeats and a target of 30 finish in a few milliseconds, thanks to break and the skip test.

Common mistakes

  • Using i > 0 instead of i > start in the skip test. A repeated coin is then skipped even when its twin was chosen one level up, so [2, 5, 2, 1, 2] with target 5 returns only [[5]].
  • Recursing with i instead of i + 1, which lets one coin be used many times (the previous problem).
  • Not sorting, so equal coins are not neighbours and duplicate handfuls appear.
  • Using continue instead of break for "too big". It stays correct but wastes time.
Your turn: exactly k numbers from 1 to 9

Find all sets of exactly k different digits from 1 to 9 that add up to n. Each digit is used at most once. For k = 3 and n = 7 the answer is [[1, 2, 4]]. Describe your approach, then write it if you like.

Compare with our answer

Same pattern, but the "coins" are the digits 1 to 9, which are already sorted and distinct, so no duplicate skipping is needed. Recurse with d + 1, stop when the path has k digits, and prune when a digit exceeds what is left.

def combination_sum3(k, n):
    res = []
    def dfs(start, left, path):
        if len(path) == k:
            if left == 0:
                res.append(path[:])
            return
        for d in range(start, 10):
            if d > left:
                break
            dfs(d + 1, left - d, path + [d])
    dfs(1, n, [])
    return res

combination_sum3(3, 9) returns [[1, 2, 6], [1, 3, 5], [2, 3, 4]]. There are at most C(9, k) leaves, so the time is tiny and space is O(k).

A strong answer mentions: ascending digits with a start index, d + 1 for single use, a length check of k, and why no duplicate skipping is needed.

Check what stuck

1. A shopper has 40 coupons (some with equal value, each usable once) and wants every distinct set of coupons worth exactly 50. Which approach fits best?

2. What does the skip test i > start and coins[i] == coins[i - 1] guarantee?

3. A learner changes i > start to i > 0 in the skip test. Which input is still answered correctly?

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