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?


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.

Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *