Problem overview
The function change receives a target amount and a slice coins of distinct coin values. It returns how many different combinations of coins add up to exactly amount, or 0 if none do. Each coin value can be used as many times as you like. A combination is defined by how many coins of each value it uses, not by their order, so 2 + 2 + 1 and 1 + 2 + 2 are the same combination.
For amount = 5 and coins = [1, 2, 5] the answer is 4: 5, 2 + 2 + 1, 2 + 1 + 1 + 1 and 1 + 1 + 1 + 1 + 1. For amount = 3 and coins = [2] it is 0, because coins of 2 only make even sums. When amount is 0 the answer is 1, the combination that uses no coins.
Approach: count sums instead of listing combinations
Listing every combination is hopeless for large inputs: a few dozen coin values can make over a billion combinations of 5000. Counting them is enough, and counting fits dynamic programming.
Let ways[a] be the number of combinations that make the sum a, for every a from 0 to amount. At the start only ways[0] is 1 (the empty combination), and everything else is 0. The answer is ways[amount].
Now add the coins one at a time. When a coin is added, every combination for a - coin, plus one more of that coin, is a combination for a. So ways[a] grows by ways[a - coin]. Going through the sums from small to large lets ways[a - coin] already include the current coin, so the same coin value can be used again and again.
The order of the two loops decides what is counted. With the coins in the outer loop, the counts so far only use the coins before the current one. Each combination is therefore built in one fixed order: all its coins of the first value, then all of the second, and so on. Each one is counted exactly once, as 1 + 3 but never as 3 + 1. If the sums were the outer loop and the coins the inner one, any coin could be the last one added to any sum, and both orders would count. The result would be the number of ordered sequences. For amount = 4 and coins = [1, 2, 3] that version returns 7 instead of 4.
The cost is O(n · amount) time, where n is the number of coins, and O(amount) space for the slice.
Step by step
- Create
wayswithmake([]int, amount+1). It needs one slot per sum from 0 toamount, andmakefills it with zeros, which is right because no positive sum can be made before any coin is added. - Set
ways[0] = 1. The sum 0 has exactly one combination: no coins. Every other combination grows from this one. - Loop over the coins with
range, dropping the index with_. This is the outer loop, which makes the counts combinations rather than orders. - Loop over the sums from
coinup toamount. A sum smaller than the coin can't contain it, and going upward lets a smaller sum already include this coin. - Add
ways[a-coin]toways[a]. This is the key line: each count is built from the counts of smaller sums. - Return
ways[amount]after the outer loop. Ifamountis 0, the inner loop never runs and this returnsways[0], which is 1.
The solution in Go
func change(amount int, coins []int) int {
ways := make([]int, amount+1)
ways[0] = 1
for _, coin := range coins {
for a := coin; a <= amount; a++ {
ways[a] += ways[a-coin]
}
}
return ways[amount]
}
Here is how ways changes for amount = 5 and coins = [1, 2, 5], from a run of this code with a print after each coin:
start [1 0 0 0 0 0]
coin 1 [1 1 1 1 1 1]
coin 2 [1 1 2 2 3 3]
coin 5 [1 1 2 2 3 4]
After the coin 1, every sum has exactly one combination (all ones). The coin 2 adds the ones that use 2s: sum 4 now has three (1+1+1+1, 2+1+1, 2+2). The coin 5 adds the single combination 5 to the last slot, giving 4.
The Go details worth a closer look:
makeand zero values.make([]int, n)creates a slice of lengthnwith every element 0, so onlyways[0]needs setting.rangeover a slice yields the index and the value. Go rejects an unused variable, so the index is written as_.- Three-part
for. Go has nowhile;for a := coin; a <= amount; a++is the counted loop, andaexists only inside it. +=reads and writes the same slice.ways[a] += ways[a-coin]reads an entry that may have been updated earlier in this same pass. That is exactly the "use the coin again" behaviour, not a bug.intis 64 bits in Go, so the counts fit easily. The lesson promises answers within 32 bits anyway. Withamount = 5000andcoins = [1, 2, 5]the function returns 1252001.
Complexity
Time: O(n · amount). Each of the n coins goes over at most amount + 1 sums, with constant work for each.
Space: O(amount). The slice ways holds amount + 1 counts, and nothing else grows with the input.
Edge cases and common mistakes
- Swapped loops. Putting the sums outside and the coins inside counts orders. For
amount = 4andcoins = [1, 2, 3]that returns 7 instead of 4. - Forgetting
ways[0] = 1. Every count then stays 0, andchange(5, []int{1, 2, 5})returns 0 instead of 4. - Amount 0. The answer is 1, whatever the coins are.
change(0, []int{7})returns 1, and so does an emptycoinsslice. - A coin larger than the amount.
change(10, []int{10})returns 1, and a coin bigger thanamountsimply doesn't enter the inner loop, because the starting value ofaalready exceedsamount. - Unreachable sums.
change(3, []int{2})returns 0: no coin ever adds to an odd index, soways[3]stays 0. - Looping the sums downward. A descending inner loop would let each coin be used at most once, which solves a different problem. The lesson needs the upward direction.
Testing
amount = 5,coins = [1, 2, 5]gives4.amount = 3,coins = [2]gives0.amount = 4,coins = [1, 2, 3]gives4.amount = 0,coins = [7]gives1.amount = 10,coins = [10]gives1.amount = 5000,coins = [1, 2, 5]gives1252001.
