Coin Change Denominations

Problem

Given some amount of money integer, and an array of integer coins, calculate the total number of ways to make change.

Approach

Suppose that we want to find the total number of denominations of 5 cents, using any U.S. coins (pennies, nickels, dimes, quarters, etc.)

Well, for 5 cents, there are two choices. You either have 5 pennies, or 1 nickel. In total, thats 2 denominations.

How about 15 cents?

\(1 + 1 + 1 ... + 1 + 1 = 15\)

\(5 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 15\)

\(5 + 5 + 1 + 1 + 1 + 1 + 1 = 15\)

\(10 + 1 + 1 + 1 + 1 + 1 = 15\)

\(5 + 5 + 5 = 15\)

\(10 + 5 = 15\)

There are 6 denominations total, as can be seen above.

Let's take a step back to the case where our money is 5 cents, and we have a penny and a nickel. Our algorithm needs to account for the case where we use the nickel once, or a penny 5 times in a row. This can be represented with the following recurrence relation:

\[T(n){i}=T(n-coins[i]){i}+ T(n)_{i+1}\]

What the formula above means is that we choose to add together our two choices here: spend the current coin at index \(i\), or refrain from using this coin and instead, choose the next coin at index \(i+1\).

Solution

With the power of Scala and recursions, we can make a function that calculates the total number of money denominations, given 2 parameters -- the amount of money and the list of allowed coins to use.

But not only that, we can also make this a one-liner!

def countChange(money: Int, coins: List[Int]): Int = if(money == 0) 1 else if(money > 0 && !coins.isEmpty) countChange(money - coins.head, coins) + countChange(money, coins.tail) else 0  

Okay, so it's not so elegant.
Here is a neater formatted version:

def countChange(money: Int, coins: List[Int]): Int = {  
    if(money == 0)
        1
    else if(money > 0 && !coins.isEmpty) 
        countChange(money - coins.head, coins) + countChange(money, coins.tail)
    else
        0
  }

The key here is the middle part with the else if condition. Since this is a recursive function, this function will be iterated many times. Majority of the time, the else if condition will be satisfied because the amount of money will never be 0 until the very end of the calculation.

The addition in countChange(money - coins.head, coins) + countChange(money, coins.tail) may ponder you. The reason why this works is strictly because of the parameters being passed into the function. In either of the countChange calls, we are either passing in less money, or fewer usable coin types. This ensures that the calls will eventually terminate, since if money == 0 the loop will return 1. The money could also be lower than 0, which means that the particular combination of coins failed to subtract the total amount of money to a nice clean 0. (i.e. If we have 25 cents, and we use up 3 dimes, we get -5 cents, meaning that 25 cents cannot be made up of 3 dimes, since the end result is not 0.)

The calls being able to terminate are nice, but that alone isn't enough. The reason why we want to add both of these countChange calls together is because we want to explore all the combinations.

Lets look at a simple example.
Suppose we have 5 cents, and suppose we can only use pennies and nickels.
When we call countChange the first time, we will go into the if-else statements and we will call the following:

countChange(5 - 1, List(1, 5)) + countChange(5, List(5))

It should be noted that the coins.head returns the front of the queue of (1, 5), which is 1 in this case. coins.tail return the list with the head detached, so it returns List(5). These head and tail functions are from the Scala List library, and they do not return the same type; they return different types.

We can already see the outcome of the second call, countChange(5, List(5)). Since it only has 1 value in the List, namely 5, that 5 will be deducted from the total amount (which is 5 at the moment) and the total money will be 0. Since the money will equal 0, 1 is returned. Therefore, this call returns 1.

Hence we can look at the previous code as the following:

countChange(5 - 1, List(1, 5)) + 1

On the left side, can we predict the outcome? Each iteration of this function behaves like traversing a binary tree. In one iteration, you either subtract the money from the coins.head, or you chop the head off the coins list. But after this call, in which we pass in the value 5 - 1 = 4 to countChange, we can see that the head can be chopped off the coins list but it will never give us a 1. Since the next element in the list is a 5, and our total money is 4, we can never make a denomnination out of this since 4 - 5 = -1. Therefore, 0 is returned, and ultimately added.

We could see that as 4 goes to 3, then goes to 2, then goes to 1, and eventually 0, the "right side of the tree", a.k.a countChange(money, coins.tail) will never, ever return 1. As for the "left side of the tree", our variable money will decrement itself by 1 until it reaches 0. As our money decrements itself by 1, it is pretty much like deducting a penny each time. Since it will eventually reach 0, because we are only deducting a penny, we would expect at most 1 denomination, solely using pennies. And this happens to be true: For five cents, we can either have five pennies, or 1 nickel. Our very first countChange(money, coins.tail) call when money = 5 returned a 1 because 5 - 5 = 0, and if (money == 0) return 1. This calculation took care of the nickel denomination. At the very end of any recursive iterations, either a 1 or 0 is returned. For this particular problem, after everything was returned, our first call turns into: 1 + 1 which would equal 2, for 2 total denominations in 5 cents with pennies and nickels.

Update: I posted the same answer here on SO: (https://stackoverflow.com/questions/12629721/coin-change-algorithm-in-scala-using-recursion/26686640#26686640)