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
- Sort the coins. Equal values become neighbours, and a coin bigger than what is left means all later coins are too big.
- Use a start index.
dfs(start, left, path)triescoins[i]forifromstart, so each combination is built in only one order. - Use each coin once. After choosing coin
i, recurse fromi + 1. - Skip repeats at the same level. If
i > startandcoins[i] == coins[i - 1], choosing it would rebuild the same handful that the earlier copy already built, socontinue. A later copy is still available deeper, becausestarthas moved on. - Prune. If
coins[i] > left,break. Because the list is sorted, nothing later can fit either. Ifleft == 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 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 (every subset) | O(n · 2^n): sum of each subset, plus sorting the matches | O(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 small | O(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
breakand the skip test.
Common mistakes
- Using
i > 0instead ofi > startin 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
iinstead ofi + 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
continueinstead ofbreakfor "too big". It stays correct but wastes time.
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.
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?
Sorting allows two prunes: an equal coupon at the same level is skipped, and a value larger than what is left ends the loop. All 2^40 subsets is about 10^12, and counting or greedy do not list the sets.
2. What does the skip test i > start and coins[i] == coins[i - 1] guarantee?
Copies of a value must be picked in order, which removes the duplicate handfuls but still allows [2, 2]: the second 2 is the first candidate one level deeper. Values can repeat in a combination, and earlier uses on the path do not block later ones.
3. A learner changes i > start to i > 0 in the skip test. Which input is still answered correctly?
The bug skips a repeated value even when its twin was chosen one level up. Inputs without repeated values are unaffected, so the last one still returns [[1, 2, 5], [1, 7], [2, 6]]. The others return [[5]], [] and [].
Score 60% or more and the lesson is marked complete.