Luís Ramalho bio photo

Luís Ramalho

Developer & Entrepreneur

Twitter LinkedIn Github Stackoverflow

Coin sums is a problem where one must count how many different ways a £2 coin can be made using any number of coins. Firstly, I tried to tackle this problem using brute-force, as I usually go about it. However, in this particular case and because there were so many coins (aka 8), creating a for loop for each and every coin was not a solution that I’d be happy with.

Thus, and because none of the algorithms that came to mind applied here I turned my eyes to other possible solutions in the www. In this research I found a very clever solution by Bradley, which introduced me to Integer Partition. If you are not familiar, basically:

In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition.

Armed with this new knowledge, I was able to easily implement the pseudo-code and obtain the right answer for the problem.

int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};
return count(200, coins.length - 1, coins);
int count(int n, int m, int[] coins) {
    if (n == 0) {
        return 1;
    }
    if (n < 0) {
        return 0;
    }
    if (m < 0 && n >= 1) {
        return 0;
    }
    return count(n, m - 1, coins) + count(n - coins[m], m, coins);
}
return result;

The full solution can be found here.