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

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

## C++

Output:

Total number of ways to get desired change is 7

## Java

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).

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

## C++

Output:

Total number of ways to get desired change is 4

## Java

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 –

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(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.     (3 votes, average: 5.00 out of 5) Loading...

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

Hi,
I don’t know how to thank you. I was looking for a variant of coin change problem that accounted permutations too. Your first code does it for me. Thanks a lot. Guest

Nice Job Guys.. Guest

can you provide any other way which is easier than this? Guest
Jay prakash

Can we implement memoization (lookup table) using array instead of using map functions. I find it difficult to implement the same with array. Plz help. Guest

how to print all these combinations as well? Guest

Hi,

Could you please provide the code for dynamic programming which includes all permutations too? Guest

This should do: https://ideone.com/Q3byNO Guest

Hello,

line number 29 on the 3rd solution is not decrementing the index, it should be

int include = count(S, n-1, N-S[n]);