The problem
Given coin values and an amount, count how many different combinations of coins add up to the amount (unlimited coins of each value; order doesn’t matter).
Input: amount = 5, coins = [1, 2, 5] Output: 4 (5, 2+2+1, 2+1+1+1, 1+1+1+1+1)
Picture it
Picture boxes ₹0 … ₹amount, each counting the ways to make that amount. We bring in one coin type at a time. When coin c arrives, every box x gains the ways of box x − c (“use one more c”). Handling coins one type at a time is what stops 1+2 and 2+1 being counted twice.
How to recognise it
- You must count the combinations that reach an exact total, not find the fewest coins.
- Order does not matter: 1 + 2 and 2 + 1 are the same combination.
- Each coin type can be used any number of times.
- The same sub-question ("how many ways to make this smaller amount?") repeats.
- An amount up to 5000 with up to 300 coin types makes listing every combination impractical.
Start with brute force
Go through the coin types in order. For each coin, either use one more copy of it, or move on to the next type for good. Count the ways that land exactly on zero.
def change_brute(amount, coins):
def go(i, remaining):
if remaining == 0:
return 1
if i == len(coins) or remaining < 0:
return 0
use = go(i, remaining - coins[i]) # take another copy of coin i
skip = go(i + 1, remaining) # never use coin i again
return use + skip
return go(0, amount)
Every call splits in two and the same (i, remaining) pairs come up again and again. With coin 1 and amount 5000 the recursion is thousands of levels deep and the number of calls grows exponentially in the number of distinct paths. Time is exponential in the worst case, and space is O(amount) for the recursion.
From brute force to the idea
- Find the waste. The pair (coin index, remaining amount) has at most 300 × 5000 possible values, but the recursion solves each of them many times.
- One box per amount. Let
ways[x]be the number of combinations that make x.ways[0] = 1, because the empty combination makes 0. - Add coin types one at a time. After handling coins c1..ck,
ways[x]counts combinations using only those types. When coin c arrives, every combination forx - cbecomes a combination for x by adding one copy of c, soways[x] += ways[x - c]. - Loop amounts upwards. Going from c up to the amount lets
ways[x - c]already include copies of c, which gives unlimited use of that coin. - Keep coins on the outside. Because one type is finished before the next begins, each combination is built in only one order (all 1s, then 2s, and so on). That is what stops 1 + 2 and 2 + 1 being counted twice.
This is the key idea: a one-dimensional table of counts, filled one coin type at a time.
The key idea
ways[x] += ways[x − c], looping coins on the outside and amounts on the inside. O(amount × coins).
Python solution
def change(amount, coins):
ways = [1] + [0] * amount
for c in coins: # one coin type at a time: no reorderings
for a in range(c, amount + 1):
ways[a] += ways[a - c]
return ways[amount]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
| Approach | Time | Space |
|---|---|---|
| Brute force | Exponential: use or skip choices without sharing results | O(amount): recursion depth |
| 1-D table (shown code) | O(amount × coins): one addition per coin per amount | O(amount): one box per amount, which replaces the full coins × amount table |
For the largest inputs that is about 1.5 million additions.
Edge cases
- Amount 0: returns 1, the empty combination, even with no coins (
change(0, [])is 1). - Amount above 0 and no coins: returns 0.
- Impossible amounts (
change(3, [2])): returns 0. - One coin equal to the amount (
change(10, [10])): returns 1. - Coin larger than the amount:
range(c, amount + 1)is empty, so the coin is ignored (change(5, [7])is 0). - Coin order in the list:
[1, 2, 5]and[5, 2, 1]both give 4. - Big counts: Python integers do not overflow, so no modulo is needed; the problem promises the result fits in 32 bits.
Common mistakes
- Swapping the loops (amounts outside, coins inside). That counts ordered sequences, so
change(5, [1, 2, 5])becomes 9 instead of 4. - Setting
ways[0] = 0, which makes every answer 0. - Looping amounts downwards, which allows each coin at most once instead of any number of times.
- Mixing this up with "fewest coins" (Coin Change), which uses
mininstead of a sum.
Each coin in the list can be used at most once. Count the combinations that make the amount. For [1, 2, 3, 4, 5] and amount 5 the answer is 3 (5, 1+4, 2+3). Describe your approach, then write it if you like.
Compare with our answer
Keep the same table and the same outer loop over coins, but run the amounts downwards. Then ways[a - c] still holds the count from before this coin, so each coin is added at most once.
def change_once(amount, coins):
ways = [1] + [0] * amount
for c in coins:
for a in range(amount, c - 1, -1): # downwards: no reuse of c
ways[a] += ways[a - c]
return ways[amount]
change_once(5, [1, 2, 3, 4, 5]) is 3, change_once(10, [5]) is 0, and change_once(0, [1]) is 1. Time O(amount × coins), space O(amount).
A strong answer mentions: reversing the inner loop direction, why the old values are still available, and that equal coin values in the list would count as different coins.
1. You need the number of different orders in which coins from [1, 2, 5] can add up to 5 (so 1 + 2 and 2 + 1 differ). Which change to the shown approach fits?
With amounts outside, every coin can be the last one added to reach a given amount, so different orders are counted separately (9 for this input). With coins outside, each combination appears in only one order.
2. Why is the shown code O(amount × coins) rather than exponential?
The table stores the number of ways for every smaller amount, so nothing is recomputed. There is no early stop or sorting: all coins are processed for every amount they fit into.
3. A learner starts with ways = [0] * (amount + 1) and leaves everything else unchanged. What does change(5, [1, 2, 5]) return?
Every update adds an earlier box to a later one, and all boxes start at 0, so the table stays 0. The running code returns 0. The base case ways[0] = 1 is the seed for every combination.
Score 60% or more and the lesson is marked complete.