Problem overview
The function change(_ amount: Int, _ coins: [Int]) -> Int receives a target sum and a list of distinct coin values. It returns how many different combinations of coins add up to exactly amount, or 0 if none does. Each coin value can be used any number of times.
The word "combination" matters. 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 one.
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] the answer is 0, since coins of 2 only make even sums. When amount is 0 the answer is 1: the combination of no coins at all.
Approach: count sums, one coin at a time
Listing every combination is hopeless for large inputs, because their number grows explosively. Counting them is enough, and the counts for small sums can be reused for larger ones.
Let ways[a] be the number of combinations that make the sum a, for every a from 0 to amount. Start with ways[0] = 1 (no coins) and every other entry at 0. The answer is ways[amount].
Now add the coins one at a time. When a coin is added, each sum a that is at least the coin's value gains every combination of a - coin plus one more of this coin. That is ways[a] += ways[a - coin]. Going through the sums upward means ways[a - coin] may already include this coin, which allows using the same coin repeatedly.
The order of the loops decides what gets counted. With the coins in the outer loop, every combination is built in one fixed order: all its coins of the first value, then all of the second, and so on. It is counted exactly once. With the sums in the outer loop and the coins inside, any coin could be the last one added to any sum, so 1 + 3 and 3 + 1 would both be counted. That counts orders, not combinations. For amount = 4 and coins = [1, 2, 3] the correct answer is 4, and that swapped version gives 7.
Here is the array for amount = 5 and coins = [1, 2, 5], after each coin:
start [1, 0, 0, 0, 0, 0]
after coin 1 [1, 1, 1, 1, 1, 1]
after coin 2 [1, 1, 2, 2, 3, 3]
after coin 5 [1, 1, 2, 2, 3, 4]
The last entry, 4, is the answer. And for amount = 4 with coins = [1, 2, 3]:
start [1, 0, 0, 0, 0]
after coin 1 [1, 1, 1, 1, 1]
after coin 2 [1, 1, 2, 2, 3]
after coin 3 [1, 1, 2, 3, 4]
Step by step
- Create
waysas avararray ofamount + 1zeros. Before any coin is added no positive sum can be made, and it is avarbecause the loops write into it. - Set
ways[0]to 1. Every combination grows from the empty one: one coin added to no coins makes a sum equal to the coin's own value. - Loop over
coinsas the outer loop. While a coin is being added, the counts so far use only the coins before it. - Loop
aoverstride(from: coin, through: amount, by: 1), the sums this coin fits in, from the smallest up. A sum below the coin's value can't contain it. - Add
ways[a - coin]toways[a]. This is the key line: each entry reuses the counts of smaller sums. - Return
ways[amount]after the outer loop. Foramount = 0the inner loops never run, and this returnsways[0], which is 1.
The solution in Swift
class Solution {
func change(_ amount: Int, _ coins: [Int]) -> Int {
var ways = [Int](repeating: 0, count: amount + 1)
ways[0] = 1
for coin in coins {
for a in stride(from: coin, through: amount, by: 1) {
ways[a] += ways[a - coin]
}
}
return ways[amount]
}
}
The Swift details worth a closer look:
[Int](repeating: 0, count: amount + 1)builds an array of that many zeros. The array is a value type, andwaysis the only name for it, so the writes inside the loops change it in place.- Why
strideand not a range.coin...amountis a closed range, and a closed range can't end before it starts. When a coin is worth more thanamount, for examplechange(3, [5]), the expressioncoin...amountwould stop the program with a run-time error.stride(from:through:by:)is simply empty in that case, so the coin is skipped, and the function returns 0. throughincludes the end.stride(from:through:by:)includesamountwhen it is reached, whilestride(from:to:by:)stops before it. Here the sumamountmust be included.Intis 64 bits. The counts are added without any cast. In Swift an overflowing+=stops the program rather than wrapping, but the lesson guarantees the counts fit in 32 bits, so a 64-bitIntis never near its limit.- Indexing is checked.
ways[a - coin]is safe becauseastarts atcoin, so the index is never negative. An index outside the array would also stop the program.
Complexity
Time: O(n · amount), where n is the number of coins. Each coin goes over at most amount + 1 sums, with a constant amount of work for each.
Space: O(amount). The ways array holds amount + 1 counts. Nothing else grows with the input.
Edge cases and common mistakes
- Swapped loops. Putting the sums outside and the coins inside counts ordered sequences.
change(4, [1, 2, 3])would give 7 instead of 4. amount = 0. The answer is 1, from the empty combination. Becauseways[0]starts at 1, no special case is needed.- A coin bigger than
amount. It can't be part of any combination.stridemakes its loop empty. For examplechange(3, [5])gives 0 andchange(10, [10])gives 1. - Starting
ways[0]at 0. Every count stays 0, since every combination grows from the empty one. - Going downward through the sums. A downward loop makes
ways[a - coin]exclude the current coin, which allows each coin only once. The lesson allows unlimited use, so the loop goes upward. - Big answers. With coins
[1, 2, 5, 10, 20, 50, 100, 200]andamount = 5000the count is 10082315214426, far beyond 32 bits. The lesson's guarantee excludes such inputs, and 64-bitIntholds this one anyway.
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 = 3,coins = [5]gives0.amount = 10,coins = [10]gives1.
