# Coin change problem

If somebody asks you to change a 10 cent coin and you have an unlimited number of 1 cent coins, 2 cent coins, and 5 cent coins, in how many ways could you exchange the 10 cent coin? For example, you could return 2 5 cent coins in exchange for the 10. Or 10 1 cent coins, or 2 5 cent coins. So these are 3 possible ways in which you could change the 10 cent coin. How many possibilites are there in total?

A bit more formal: Given a list of numbers (the coin values) cv = {v1, v2, ..vn} and a given number N, (the coin to be changed), what is C(N), the number of possible combinations of the coin values that sum up to N?

The key to answering this question is to realize that for each coin value, vi, the number of possible combinations that sum up to N is the number of combinations for that value that we have already found previously for that number plus all those combinations that we have already found for the number N-vi. The latter is true, because if we can express the number N-vi by a combination of vi’s then, we can take each of those and by adding vi we have a valid combination for N. For example if we are looking at the coin value v2 which is 2 and N is 4, we know that 4=2+N(4-2). If we had already found out that there are two ways in which we can express 2 with our vi’s, namely by either two one cent coins or by one two cent coin, we would know that there must also be two ways in which we can express 4: by just adding a 2 cent coin to the two one cent coins or by adding a two to the one two cent coin.

We have thus found out that the problem for N can be expressed in terms of N-1 + some increment. So we know we can implement this is either iteratively, starting with 1 and building up the computations to N, or recursively, i.e. starting with N and drilling down to 1.

Here we show a recursive implementation in Scala.

know th express more in case we can express N in terms of vi: C(N) = C(N-vi) + C(N).

For example let N=4 and cv=[1,3]. Lets start with v1=1. Can the number 4 be expressed in terms of 1s? Well, it can, if the number 3 (so 1 less than 4, because we are looking at the coin with value 1) can be expressed as a sum of any of the other values, because then we just take that sum and add one to arrive at 7. So if we had already found out, that we can express the number 3 with two different combinations of our given coin values (one option is 3 coins of 1 cent, or one 3 cent coin), then we know, that there are also 2 possiblilities for the number 4.

Alternatively you could start with the coin value 3, i.e. cv. The number 7 can be expressed as a sum of 3 plus the number of combinations that we have found for 4.

This is a perfect fit for dynamic programming. But how can we find a solution? First we realize that only those coins are to be considered whose value is <=N. If we had 20 cent coints they would be of no use if we wanted change for a 10 cent coin. So those >N can be discarded. Then we realize that if we look at a certain coin, e.g. 3, and we want to know if we can build a composition of 3s to sum up to 10, we find that the best we can do with only 3s is to sum up to 9. So 10-9=1 is still missing. If we can find other coins that can be combined to sum to 1, we can use that and have a valid combination of 3s and that found number. So the procedure is as follows: We loop over all the coin values we have, here [1,3,5] and for each of those values we check if we can build a combination whose sum is equal to any of the number <=10. For example, we start with the coin value 1. The numbers that are <= 12 are all the numbers [1,2,3,..12]. I call this list twelver_list, just to have a name. Can we sum ones to get a one? Sure, so we remember this information by writing down {1:1}, which is supposed to mean that we found on combination of our values that sums to one. Then we check the next number, 2. Can we sum ones to get a two? Of course, so {1:1, 2:1}. Then the next number, 3, which results in {1:1, 2:1, 3:1} and so forth. Since all the numbers from 1 to 12 can be described by a sum of ones the final list is {1:1, 2:1, 3:1, 4:1, 5:1, 6:1, 7:1, 8:1, 9:1, 10:1}. So now we are done with our first coin. The second coin value is 3. So again we look at all the numbers <= 12 and find out which of those can be described by a sum of threes. But as already mentioned, we know that if a number in the twelver_list divided by 3 has a rest, and we already found this rest can be described by a combination of previously checked coin values, than we know we have found another possible combination. For example, we check if the number 1 in the twelver_list can be described by 3s. Of course not, since 3 >1. The same holds for 2. Number 3 can be perfectly described by 3, so our array in which we remember our found combinations changes to this: {1:1, 2:1, 3:2, 4:1, 5:1, 6:1, 7:1, 8:1, 9:1, 10:1}. Then we check number 4. All combinations for number 4 are those previously found plus one if we can express 4 by the coin value 3 and another valid coin value combination, so 4-3 has the rest one and we check if we can express 1 by another coin, which we can, namely the 1 cent coin. So yay, found another combination: {1:1, 2:1, 3:2, 4:2, 5:1, 6:1, 7:1, 8:1, 9:1, 10:1}. The same holds true for number 5. But now we look at number 6. The 3 cent coin leaves 6-3=3. So the number of combinations for number 6 is the number of all combinations found for 3 plus 6=3+3, so we update our number of combinatios by one. However, we have already found out, there are 2 possible combinations for number 3, and since 6 is the sum of 2 3s it is also the sum of 2 of the combinations of 3s. Thus, there a Continuing with this we get {1:1, 2:1, 3:2, 4:2, 5:2, 6:3 7:2, 8:2, 9:2, 10:2}.