Python Algorithms – Maximum combinations of coins

Sometimes complicated algorithms are really easy to be written down. The current problem is solved in 6 lines of code (from line 5 to line 11), but it you need to put effort to understand how the algorithm works and what are the dependencies built-in it.

Let’s start with the very beginning. This time, the description of the problem is really simple and understandable. It is located here and looks like this:

Change
Implement a program which finds all possible ways of building a sum out of different coins. The coins you have are of value 1, 2, 5, 10, 20, 50 and 100.
Input: The input consists of a single line that contains the goal sum S.
Output: Output the number of ways this sum could be build using coins of any value amongst 1, 2, 5, 10, 20, 50 and 100. You could use as many coins as you want from any value.
Limits: 1 <= S <= 1000
Input: 25
Output: 68

What do we need to do? Actually, we need to find the dependencies of the result to the coins. E.g. how can we count 68 outputs for the sum of 25? Initially I have started to build a picture, telling me how each number can be represented in coins (e.g. 5 can be represented in four different ways -> 1+1+1+1+1 or 1+1+1+2 or 1+2+2 or 5). After some time, the dependency was found. One should take a good look at the table below, to understand how it works. The arrows show what kind of numbers are used to form the next number:

E.g., with coins of value 1, you have only one way to represent each number. (5 can be represented as 1+1+1+1+1, 3 can be represented as 1+1+1). When we add the possibility of having coin of value 2, then we increase by one the possibilities at 2 and later we sum the value of each position of the array with the value of k positions before it. (k is the value of the latest introduced coin).

Probably, if you start looking at the code, you will understand what I mean. Or not. Anyway, give it a try:

The code is also available in GitHub here.

🙂