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

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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <bits/stdc++.h> using namespace std; // Function to find the total number of ways to get change of N // from unlimited supply of coins in set S int count(int S[], int n, int N) { // if total is 0, return 1 if (N == 0) return 1; // return 0 if total become negative if (N < 0) return 0; // initialize total number of ways to 0 int res = 0; // do for each coin for (int i = 0; i < n; i++) { // recuse to see if total can be reached by including // current coin S[i] res += count(S, n, N - S[i]); } // return total number of ways return res; } // main function int main() { // n coins of given denominations int S[] = { 1, 2, 3 }; int n = sizeof(S) / sizeof(S[0]); // Total Change required int N = 4; cout << "Total number of ways to get desired change is " << count(S, n, N); return 0; } |

**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

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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <bits/stdc++.h> using namespace std; // Function to find the total number of distinct ways to get change of N // from unlimited supply of coins in set S int count(int S[], int n, int N) { // if total is 0, return 1 (solution found) if (N == 0) return 1; // return 0 (solution do not exist) if total become negative or // no elements are left if (N < 0 || n < 0) return 0; // Case 1. include current coin S[n] in solution and recurse // with remaining change (N - S[n]) with same number of coins int include = count(S, n, N - S[n]); // Case 2. exclude current coin S[n] from solution and recurse // for remaining coins (n - 1) int exclude = count(S, n - 1, N); // return total ways by including or excluding current coin return include + exclude; } // main function int main() { // n coins of given denominations int S[] = { 1, 2, 3 }; int n = sizeof(S) / sizeof(S[0]); // Total Change required int N = 4; cout << "Total number of ways to get desired change is " << count(S, n - 1, N); return 0; } |

**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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include <bits/stdc++.h> using namespace std; // create a map to store solutions of subproblems unordered_map<string, int> lookup; // Function to find the total number of distinct ways to get change of N // from unlimited supply of coins in set S int count(int S[], int n, int N) { // if total is 0, return 1 (solution found) if (N == 0) return 1; // return 0 (solution do not exist) if total become negative or // no elements are left if (N < 0 || n < 0) return 0; // construct a unique map key from dynamic elements of the input string key = to_string(n) + "|" + to_string(N); // if sub-problem is seen for the first time, solve it and // store its result in a map if (lookup.find(key) == lookup.end()) { // Case 1. include current coin S[n] in solution and recurse // with remaining change (N - S[n]) with same number of coins int include = count(S, n, N - S[n]); // Case 2. exclude current coin S[n] from solution and recurse // for remaining coins (n - 1) int exclude = count(S, n - 1, N); // assign total ways by including or excluding current coin lookup[key] = include + exclude; } // return solution to current sub-problem return lookup[key]; } // main function int main() { // n coins of given denominations int S[] = { 1, 2, 3 }; int n = sizeof(S) / sizeof(S[0]); // Total Change required int N = 4; cout << "Total number of ways to get desired change is " << count(S, n - 1, N); return 0; } |

**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 🙂