Coin Change Problem

Given coins of different denominations and a total amount of money, find the number of combinations that makes up that amount. ​For example, given unlimited coins in 1, 2, 4 denominations, how many combinations are there to make up the amount of 12?

Thought Process

Given coins in different denominations, we'd solve this problem by breaking it into sub-problems which means given coins in less different denominations. The answer to the problem of given coins in n different denominations is based on solving the problem of given coins in (n-1) different denominations, and the answer to the problem of coins in (n-1) different denominations is based on solving the problem of coins in (n-2) different denominations.

We can use an array named combination to store the number of combinations that make up the amount. For example, the number of combinations to make up the amount of 1 is stored combination[1], and the combinations to make up the amount of 12 is stored in combination [12].

The number of combinations to make up a given amount is equal to the number of combinations before a coin denomination is added to the picture, plus the number of combinations after such a coin denomination is added to the picture for the amount of "amount - coin". 

When adding the first coin to the picture, we'd calculate this array - combination. When adding the 2nd coin to the picture, the same combination[amount] is being calculated based on the following pseudocode:   

Code Editor

Read More