## Project Euler: Problem 31 – Coin sums

#### Problem 31:

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1x£1 + 1x50p + 2x20p + 1x5p + 1x2p + 3x1p

How many different ways can £2 be made using any number of coins?

#### Idea:

I had no idea how I was going to go about this, so I started researching a similar problem I did a while back in college (how many ways can you make change for a dollar?). Stumbled upon Integer Partitions.

```int answer = -1;

int[] denomination = {1,2,5,10,20,50,100,200};

//==================================
private static int integerPartition(int target, int index, int[] denoms) {
if(target == 0) {
return 1;
}
if(target < 0) {
return 0;
}
if(index < 0 && target > 0) {
return 0;
}
return integerPartition(target,index-1,denoms) +
integerPartition(target-denoms[index], index,denoms);
}```

In my research, I found this is a form of Integer Partition and came across this link.