Coin change-making problem (unlimited supply of coins)

Given an unlimited supply of coins of given denominations, find the minimum number of coins required to get a desired change.

 
For example, consider S = { 1, 3, 5, 7 }
 

If desired change is 15, the minimum number of coins required is 3

(7 + 7 + 1) or (5 + 5 + 5) or (3 + 5 + 7)

 

If desired change is 18, the minimum number of coins required is 4

(7 + 7 + 3 + 1) or (5 + 5 + 5 + 3) or (7 + 5 + 5 + 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 including the coin or not. If choosing the current coin resulted in the solution, we update the minimum number of coins needed. Finally, we return minimum value we get after exhausting all combinations.

 
C++ implementation –
 

Download   Run Code

Output:

Minimum number of coins required to get desired change is 4

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

 


 

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 n. We know that problems having optimal substructure and overlapping subproblems can be solved by dynamic programming, in which subproblem solutions are saved rather than computed again and again.

In method is illustrated below, we uses bottom-up approach i.e., we solve smaller sub-problems first, then solve larger sub-problems from them. It computes T[i], for each 1 <= i <= N, which stores minimum number of coins needed to get total of i. It make use of smaller values of i already computed and has the same asymptotic run-time as Memoization but no recursion overhead.

 
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(n2) and auxiliary space used by the program is O(n).

 
Exercise: Find minimum number of coins required 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 🙂