# 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

 ```1 ``` `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

 ```1 ``` `count`
initialized to 0.

This gives us the basic structure below:

### 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:

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

 ```1 ``` `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```:

### 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

 ```1 ``` `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```.

### Inside the Recursive Function

 ```1 ``` `coins`
array. Let’s access this coin with the index and save it to ```1 currentCoin```.

Now that we have

 ```1 ``` `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.

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

 ```1 ``` `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.

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

### Freaq Out!

## The `freaq` bookmarkletOne of my students, Zach Pomerantz, created a bookmarklet called [freaq](http://www.freaq.io/) that is an audio...… Continue reading

#### Bitwise N-Queens

Published on May 08, 2014

#### Flooring a Number

Published on May 06, 2014