Coin Change Problem (Total number of ways to get the denomination of coins)

Given an unlimited supply of coins of given denominations, find the total number of distinct ways to get a desired change.

For example,

 
Input: S = { 1, 3, 5, 7 }, N = 8
 
Total number of ways is 6

{ 1, 7 }
{ 3, 5 }
{ 1, 1, 3, 3 }
{ 1, 1, 1, 5 }
{ 1, 1, 1, 1, 1, 3 }
{ 1, 1, 1, 1, 1, 1, 1, 1 }

 

Input: S = { 1, 2, 3 }, N = 4

Total number of ways is 4

{ 1, 3 }
{ 2, 2 }
{ 1, 1, 2 }
{ 1, 1, 1, 1 }

 


 

The idea is to use recursion to solve this problem. For each coin of given denominations, we recuse to see if total can be reached by choosing the coin or not. If choosing the current coin results in the solution, we update total number of ways.

 
C++ implementation –
 

Download   Run Code

Output:

Total number of ways to get desired change is 7

 
The time complexity of above solution is exponential as each recursive call is making n recursive calls.
 


 
There is some issue with the above solution. Above solution doesn’t always returns distinct sets. For example, for set {1, 2, 3} it returns 7 as some ways are permutations of each other as shown below –

{1, 1, 1, 1}

{1, 1, 2}, {2, 1, 1}, {1, 2, 1}

{2, 2}

{1, 3}, {3, 1}

 


 
How can we get distinct ways?
 

The idea is somewhat similar to Knapsack problem. The problem can be recursively defined as –

    count(S, n, total) = count(S, n, total-S[n]) + count(S, n-1, total);

 

That is, for each coin

1. We include current coin S[n] in solution and recurse with remaining change (total – S[n]) with same number of coins.

2. We exclude current coin S[n] from solution and recurse for remaining coins (n – 1).
 

Finally, we return total ways by including or excluding current coin. The base case of the recursion is when solution is found (i.e. change becomes 0) or the solution doesn’t exist (when no coins are left or total becomes negative).

 
C++ implementation –
 

Download   Run Code

Output:

Total number of ways to get desired change is 4

 
The time complexity of above solution is still exponential and auxiliary space used by the program is O(1).
 


 

The problem has an optimal substructure as the problem can be broken down into smaller subproblems which can further be broken down into yet smaller subproblems, and so on. The problem also clearly exhibits overlapping subproblems so we will end up solving the same subproblem over and over again. The repeated sub-problems can be seen by drawing recursion tree for higher values of desired change. We know that problems having optimal substructure and overlapping subproblems can be solved using dynamic programming, in which subproblem solutions are Memoized rather than computed again and again. The approach is illustrated below –

 
C++ implementation –
 

Download   Run Code

Output:

Minimum number of coins required to get desired change is 4

 
The time complexity of above solution is O(nN) and auxiliary space used by the program is O(nN).

 
Exercise:
1. Write bottom-up version of above memoized solution.
2. Find total number of ways to get a desired change from limited supply of coins of given denominations.
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂