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 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.
The full solution can be found here.