Use the coin again, or move on
Count the ways to make an amount from coins you may reuse, by either using the current coin once more or moving on to the next coin. About 15 minutes.
Stay or advance
How many ways can you make 5 from coins of 1, 2 and 5, using each kind as often as you like? The order of the coins doesn't matter: 1 + 2 + 2 is the same as 2 + 1 + 2.
To count each combination once, go through the kinds of coin in order. For the current kind, either use one more of it, which keeps you on the same kind, or stop using it for good and move on to the next kind. Two branches again.
def reach(i, left):
if left == 0:
return True
if i == len(items):
return False
take = reach(i + 1, left - items[i])
return take or reach(i + 1, left)With only 1s: stay on coin 1 four times reaches zero. That is one way: 1+1+1+1.
Three ending cases
A call ends in one of three ways. If the amount left is exactly zero, you have built a combination: that is one way, whatever coins remain unused. If the amount left is negative, you overshot, so nothing. If you've run out of coin kinds with some amount still left, nothing.
Check them in that order, zero first. A call with zero left and no coins left still counts as a way, which is why zero is tested before running out.
How many ways make 3 from the coins 1 and 2?
- A2: 1+1+1 and 1+2
- B3
- C1
Show the answer
2: 1+1+1 and 1+2. Order doesn't matter, so 1+2 and 2+1 are the same combination.
Ways to make change
coins is a list of different positive coin values, and each value can be used as many times as you like. Count the combinations of coins that add up to amount, where the order of the coins does not matter (1 + 2 and 2 + 1 are the same). The amount 0 can be made in exactly one way (no coins).
coins = [1, 2, 5], amount = 5 → 4
0 ≤ coins ≤ 5 · 1 ≤ coin ≤ 30 · 0 ≤ amount ≤ 30