**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}; answer = integerPartition(200,denomination.length-1,denomination); System.out.println("Answer: "+answer); //================================== 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.