Problem overview
The method change receives a target amount and an array coins of distinct coin values. It returns the number of combinations of coins that add up to exactly amount, or 0 if none do. Each coin value can be used any number of times. A combination counts how many coins of each value it uses, not 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, since 2s only make even sums. For amount = 0 it is 1: the combination with no coins at all.
Approach: count sums, one coin at a time
Listing every combination is hopeless: a few dozen coins can make over a billion combinations of 5000. The method counts them instead. Let ways(a) be the number of combinations that make the sum a, for every a from 0 to amount. The answer is ways(amount).
The array starts with ways(0) = 1, the empty combination, and zeros elsewhere. Then the coins are added one at a time. When a coin is added, every combination for the sum a - coin, plus one more of this coin, is a combination for a. So ways(a) grows by ways(a - coin).
Two choices in the loops decide what the numbers mean:
- The sums go upward. When
ways(a - coin)is read, it may already include the current coin, so the same coin can be used again and again. - The coins are the outer loop. While a coin is being added, the counts so far use only the coins before it. Every combination is therefore built in one fixed order: all its coins of the first value, then the second, and so on. That makes each combination counted exactly once. 1 + 3 is counted and 3 + 1 never is.
Here is the array for amount = 5 and coins = [1, 2, 5] after each coin, for sums 0 to 5:
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
With only 1s there is one way to make every sum. Adding 2s makes 5 reachable as 2 + 2 + 1 and 2 + 1 + 1 + 1 besides 1 + 1 + 1 + 1 + 1, which is 3 ways. The 5 coin adds the single coin 5, for 4.
Step by step
- Create
waysas aval, anew Array[Int]of sizeamount + 1, so that every sum from 0 toamounthas a slot. A newArray[Int]starts filled with zeros, which is right: before any coin is added, no positive sum can be made. - Set
ways(0)to 1. The sum 0 has exactly one combination, the empty one. Every other combination grows from it. Scala indexes arrays with parentheses. - Loop over the coins with
coin <- coins. This is the outer loop, which is what turns the count into combinations. - Loop over the sums with
a <- coin to amount. Sums smaller than the coin cannot contain it. Going up lets a smaller sum already include this coin. - Add
ways(a - coin)toways(a)with+=. This is the key line: each entry reuses the counts for smaller sums. - Finish with
ways(amount)as the last expression of the method.
The solution in Scala
class Solution {
def change(amount: Int, coins: Array[Int]): Int = {
val ways = new Array[Int](amount + 1)
ways(0) = 1
for (coin <- coins) {
for (a <- coin to amount) {
ways(a) += ways(a - coin)
}
}
ways(amount)
}
}
The Scala details worth a closer look:
coin to amountincludes both ends.tobuilds an inclusive range, whileuntilexcludes the end. Whencoinis larger thanamountthe range is empty, for example(10 to 5).toListisList(), so a coin that is too big does nothing.ways(a) += ...on an array element.+=is shorthand forways(a) = ways(a) + .... The array is aval, but its elements are mutable: thevalonly fixes which array the name refers to.- Parentheses, not brackets. Array access in Scala is
ways(a), an ordinary method call. Square brackets are for type parameters, as inArray[Int]. - The last expression is the result. The method ends with
ways(amount)and noreturn. Aforloop is a statement that gives no useful value, so the loops can sit above it. Intis enough. It is a 32-bit integer that wraps silently on overflow, and the lesson guarantees that the answer, and the count for every smaller amount, fits.
Complexity
Time: O(n * amount), where n is the number of coins. Each coin goes over at most amount + 1 sums, with constant work for each.
Space: O(amount). The array has amount + 1 counts, and the loops need only a few variables.
Edge cases and common mistakes
- Amount 0. The inner loops never run for a positive coin, since
coin to 0is empty, and the method returnsways(0), which is 1.change(0, Array(7))gives 1. - No way to make the amount.
change(3, Array(5))gives 0: the coin is too big, the range is empty, andways(3)stays 0.change(3, Array(2))also gives 0. - A coin equal to the amount.
change(10, Array(10))gives 1, the single coin. - Swapping the loops. Putting the sums outside and the coins inside counts orders, not combinations. This version gives 7 for
amount = 4andcoins = [1, 2, 3], where the correct answer is 4:
Now any coin can be the last one added to any sum, so 1 + 3 and 3 + 1 are both counted.for (a <- 1 to amount) { for (coin <- coins) { if (coin <= a) ways(a) += ways(a - coin) } } - Looping the sums downward. That reads
ways(a - coin)before the current coin has been added to it, so each coin can be used at most once. - Starting
ways(0)at 0. Then nothing is ever added, and every answer is 0.
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 = 3,coins = [5]gives0.
