# 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 recurse 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.

Below is C++ and Java implementation of the idea:

## C++

Output:

Minimum number of coins required to get desired change is 4

## Java

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.

Below is C++ and Java implementation of the idea:

## C++

Output:

Minimum number of coins required to get desired change is 4

## Java

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.

(3 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest
Amit V Chavan

Your blog is just incredible. Thank you for doing this.

Guest

Thanku so much
I absolutely love this

Guest

Can Someone explain me this testcase?

denominations = {10,6,1} , sum = 18
I thought correct output is 4 (10 +6+1+1 =18)
But the output as per this code is 3.

What am i missing? Can someone explain this to me?