Coin Sums

The Problem

How many possible ways can you make change for 2£ given the following English coins: 1p, 2p, 5p, 10p, 20p, 50p, 1£ (100p), 2£ (200p)?

One example output would be: 5 x 1p, 5 x 2p, 1 x 5p, 1 x 10p, 1 x 20p, 1 x 50p, 1 x 1£

Understanding the Problem

This problem deals with the possible permutations of coins that equal 2£. However, it is not a pure combinatorics problem like Rock Paper Scissors because we do not want duplicates (1 x 1p,1 x 2p is the same as 1 x 2p,1 x 1p and therefore we should only count one of these as a possible combinations.)

Let’s start off by looking at a smaller version of this problem. Imagine that we have only 3 different types of coins - 1p, 5p, and 10p - and we’re trying to make ‘piles’ of coins that sum up to 20p. What are the possible coin combinations that we can make?

Number of coins of each type used:

10p -	- 5p -	- 1p
0	0	20
0	1	15
0	2	10
0	3	5
0	4	0
1	0	10
1	1	5
1	2	0
2	0	0

There is a pattern here. Looking at the first row of this table, we might think of this problem as starting by looking the largest-valued coin (10p) with 20p value needed to reach the total and adding none of this type of coin, and then looking at the next-largest-valued coin (5p) with still 20p value needed and adding none of this type of coin, and then finally getting to the 1p coin and iterating through to add 20 x 1p coins to reach the total of 20p. Now look at the second row of the table. We look at the largest-valued coin (10p) with 20p value needed to reach the total and adding none of this type of coin, and then looking at the next-largest-valued coin (5p) with still 20p value needed and add one of this type of coin, and then finally getting to the 1p coin and iterating through to add 15 x 1p coins to reach the total of 20p. In Javascript, this pattern looks like it could be represented by a series of nested for loops.

The Code

Let’s translate this problem into Javascript and write a function called

1	makeChange

Input and Output

The argument of the function is a variable called

total

. Since our goal is for the coins to sum up to 2£ (or 200p), we’ll call

1
makeChange

with 200.

The return value is the number of possible ways to make change for the total. This will be represented as a counter named

count

initialized to 0.

This gives us the basic structure below:

var makeChange = function(total) {

  var coins = [1,2,5,10,20,50,100,200];
  var count = 0;

  return count;
};

makeChange(200);

To Iterate or to Recurse?

An iterative approach requires that we hard-code each of the type of coins in their own for loop. An iterative solution might look something like the following:

var makeChange = function(total) {

  var coins = [1,2,5,10,20,50,100,200];
  var count = 0;

  for (var a = total; a >= 0; a -= coins[coins.length-1]) {
    for (var b = a; b >= 0; b -= coins[coins.length-2]) {
      for (var c = b; c >= 0; c -= coins[coins.length-3]) {
        for (var d = c; d >= 0; d -= coins[coins.length-4]) {
          for (var e = d; e >= 0; e -= coins[coins.length-5]) {
            for (var f = e; f >= 0; f -= coins[coins.length-6]) {
              for (var g = f; g >= 0; g -= coins[coins.length-7]) {
                count++;
              }
            }
          }
        }
      }
    }
  }
  return count;
};

makeChange(200);

Note that the

1	coins[coins.length-1]

notation looks a little strange, but the idea is to show the similarities between this iterative solution and the solution coming in the section below.

The iterative function works but it’s not very elegant. In fact, the coin sums problem can easily be divided into a series of similar subproblems - get all the combinations of coins with just 1p coins, all the combinations with 1p and 2p coins, all the combinations with 1p, 2p, and 5p coins, etc - and a problem like this is perfect for a recursive function.

The Recursive Function

The basic structure

We’ll put a recursive subroutine called

changer

instead of the nested for loops. This function would go where the for loops were in the iterative solution and be called at the end of

1
makeChange

var makeChange = function(total) {

  var coins = [1,2,5,10,20,50,100,200];
  var count = 0;
 
  var changer = function() {
    // our recursive function
  };

  changer();
  return count;
};

makeChange(200);

Arguments

There are two things that we need to keep track of with each call of our recursive function. We’ll want to make these arguments of the recursive function.

First, we need to know which type of coin we’re adding to our pile. In the iterative version, we keep track of this in the decrement at every level of for loops. Here, we’ll use

index

to know which coin in the

1
coins

array we’re working with. Second, as we add coins to our pile, we need to keep track of the value still needed to reach the

1
total

. In the iterative version, we do this by initializing the variable in each nested loop to the value of the previous loop (as in var b = a, var c = b, etc.) In this recursive version, we save this information in a variable called

1
valueLeft

and we’ll initially set it to

1
total

  var changer = function(index, valueLeft) {
    // our recursive function
  }
  changer(coins.length-1, total);

Inside the Recursive Function

We’ve already decided that we’ll start with the highest-valued coin and work backwards through the

coins

array. Let’s access this coin with the index and save it to

1
currentCoin

    var currentCoin = coins[index];

Now that we have

coinsLeft

1
valueLeft

, and

1
currentCoin

, we can start creating ‘piles’ of coins that add up to

1
total

. We can do this by calling the recursive function with a copy of

1
coinsLeft

and

1
valueLeft

, moving our way deep into the

1
coinsLeft

array just as we moved deep into the nested for loops.

    while(valueLeft >= 0) {
      // call the function with the new index and the total value still needed
      // this goes maximally deep (to the 1p pieces) before doing anything else
      changer(index-1, valueLeft);
      // reduce the total value still needed by the value of the coin popped
      valueLeft -= currentCoin;
    }

But when do we increment our counter and capture the number of possible ways to reach the total? This is done when the index of

coins

reaches 0 (we’ve tried putting all the types of coins in the pile) and we’re not going over the total (we can make up the rest of the

1
value

needed with the

1
currentCoin

without a remainder). Once we reach this point, we want to return out of the loop.

    if (index === 0) {
      if (value % currentCoin === 0) {
        count++;
      }
      return;
    }

Putting this all together, we get the final code like below:

var makeChange = function(total){
  var count = 0;
  var coins = [1, 2, 5, 10, 20, 50, 100, 200];

  var changer = function(index, value){

    var currentCoin = coins[index];

    if( index === 0){
      if( value % currentCoin === 0){
        count++;
      }
      return;
    }

    while( value >= 0 ){
      changer(index-1, value);
      value -= currentCoin;
    }
  }
  changer(coins.length-1, total);
  return count;
};

makeChange(200);