Coin Change Problem
Given an unlimited supply of coins of given denominations, find the total number of distinct ways to get the desired change.
For example,
The 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 }, target = 4
The 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. We recur to see if the total can be reached by choosing the coin or not for each coin of given denominations. If choosing the current coin results in the solution, update the total number of ways.
Following is the C++, Java, and Python implementation of the idea:
C++
|
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 <iostream> #include <vector> using namespace std; // Function to find the total number of ways to get a change of `target` // from an unlimited supply of coins in set `S` int count(vector<int> const &S, int target) { // if the total is 0, return 1 if (target == 0) { return 1; } // return 0 if total becomes negative if (target < 0) { return 0; } // initialize the total number of ways to 0 int result = 0; // do for each coin for (int c: S) { // recur to see if total can be reached by including current coin `c` result += count(S, target - c); } // return the total number of ways return result; } // Coin Change Problem int main() { // `n` coins of given denominations vector<int> S = { 1, 2, 3 }; // total change required int target = 4; cout << "The total number of ways to get the desired change is " << count(S, target); return 0; } |
Output:
The total number of ways to get the desired change is 7
Java
|
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 |
class Main { // Function to find the total number of ways to get a change // of `target` from an unlimited supply of coins in set `S` public static int count(int[] S, int target) { // if the total is 0, return 1 if (target == 0) { return 1; } // return 0 if total becomes negative if (target < 0) { return 0; } // initialize the total number of ways to 0 int result = 0; // do for each coin for (int c: S) { // recur to see if total can be reached by including current coin `c` result += count(S, target - c); } // return the total number of ways return result; } public static void main(String[] args) { // `n` coins of given denominations int[] S = { 1, 2, 3 }; // total change required int target = 4; System.out.println("The total number of ways to get the desired change is " + count(S, target)); } } |
Output:
The total number of ways to get the desired change is 7
Python
|
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 |
# Function to find the total number of ways to get a change of `target` from an # unlimited supply of coins in set `S` def count(S, target): # if the total is 0, return 1 if target == 0: return 1 # return 0 if total becomes negative if target < 0: return 0 # initialize the total number of ways to 0 result = 0 # do for each coin for c in S: # recur to see if total can be reached by including current coin `c` result += count(S, target - c) # return the total number of ways return result if __name__ == '__main__': # `n` coins of given denominations S = [1, 2, 3] # total change required target = 4 print('The total number of ways to get the desired change is', count(S, target)) |
Output:
The total number of ways to get the desired change is 7
The time complexity of the above solution is exponential since each recursive call is making n recursive calls. It also requires additional space for the call stack.
There is an issue with the above solution. The above solution doesn’t always return 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, 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 the Knapsack problem. We can recursively define the problem as:
That is, for each coin.
- Include current coin
S[n]in solution and recur with remaining changetotal-S[n]with the same number of coins. - Exclude current coin
S[n]from solution and recur for remaining coinsn-1.
Finally, return the total ways by including or excluding the current coin. The recursion’s base case is when a solution is found (i.e., change becomes 0) or the solution doesn’t exist (when no coins are left, or total becomes negative). Following is the C++, Java, and Python implementation of the idea:
C++
|
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 <iostream> #include <vector> using namespace std; // Function to find the total number of distinct ways to get a change of `target` // from an unlimited supply of coins in set `S` int count(vector<int> const &S, int n, int target) { // if the total is 0, return 1 (solution found) if (target == 0) { return 1; } // return 0 (solution does not exist) if total becomes negative, // no elements are left if (target < 0 || n < 0) { return 0; } // Case 1. Include current coin `S[n]` in solution and recur // with remaining change `target-S[n]` with the same number of coins int include = count(S, n, target - S[n]); // Case 2. Exclude current coin `S[n]` from solution and recur // for remaining coins `n-1` int exclude = count(S, n - 1, target); // return total ways by including or excluding current coin return include + exclude; } // Coin Change Problem int main() { // `n` coins of given denominations vector<int> S = { 1, 2, 3 }; int n = S.size(); // total change required int target = 4; cout << "The total number of ways to get the desired change is " << count(S, n - 1, target); return 0; } |
Output:
The total number of ways to get the desired change is 4
Java
|
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 |
class Main { // Function to find the total number of distinct ways to get // a change of `target` from an unlimited supply of coins in set `S` public static int count(int[] S, int n, int target) { // if the total is 0, return 1 (solution found) if (target == 0) { return 1; } // return 0 (solution does not exist) if total becomes negative, // no elements are left if (target < 0 || n < 0) { return 0; } // Case 1. Include current coin `S[n]` in solution and recur // with remaining change `target-S[n]` with the same number of coins int incl = count(S, n, target - S[n]); // Case 2. Exclude current coin `S[n]` from solution and recur // for remaining coins `n-1` int excl = count(S, n - 1, target); // return total ways by including or excluding current coin return incl + excl; } // Coin Change Problem public static void main(String[] args) { // `n` coins of given denominations int[] S = { 1, 2, 3 }; // total change required int target = 4; System.out.print("The total number of ways to get the desired change is " + count(S, S.length - 1, target)); } } |
Output:
The total number of ways to get the desired change is 4
Python
|
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 |
# Function to find the total number of distinct ways to get a change of `target` # from an unlimited supply of coins in set `S` def count(S, n, target): # if the total is 0, return 1 (solution found) if target == 0: return 1 # return 0 (solution does not exist) if total becomes negative, # no elements are left if target < 0 or n < 0: return 0 # Case 1. Include current coin `S[n]` in solution and recur # with remaining change `target-S[n]` with the same number of coins incl = count(S, n, target - S[n]) # Case 2. Exclude current coin `S[n]` from solution and recur # for remaining coins `n-1` excl = count(S, n - 1, target) # return total ways by including or excluding current coin return incl + excl # Coin Change Problem if __name__ == '__main__': # `n` coins of given denominations S = [1, 2, 3] # total change required target = 4 print('The total number of ways to get the desired change is', count(S, len(S) - 1, target)) |
Output:
The total number of ways to get the desired change is 4
The time complexity of the above solution is still exponential and requires auxiliary space for the call stack.
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 subproblems can be seen by drawing a recursion tree for higher values of the desired change. We know that problems with optimal substructure and overlapping subproblems can be solved using dynamic programming where the subproblem solutions are memoized rather than computed and again.
Following is the C++, Java, and Python implementation of the idea:
C++
|
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 59 60 61 62 |
#include <iostream> #include <vector> #include <unordered_map> #include <string> using namespace std; // Function to find the total number of distinct ways to get a change of `target` // from an unlimited supply of coins in set `S` int count(vector<int> const &S, int n, int target, auto &lookup) { // if the total is 0, return 1 (solution found) if (target == 0) { return 1; } // return 0 (solution does not exist) if total becomes negative, // no elements are left if (target < 0 || n < 0) { return 0; } // construct a unique map key from dynamic elements of the input string key = to_string(n) + "|" + to_string(target); // if the subproblem 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 recur // with remaining change `target-S[n]` with the same number of coins int include = count(S, n, target - S[n], lookup); // Case 2. Exclude current coin `S[n]` from solution and recur // for remaining coins `n-1` int exclude = count(S, n - 1, target, lookup); // assign total ways by including or excluding current coin lookup[key] = include + exclude; } // return solution to the current subproblem return lookup[key]; } // Coin Change Problem int main() { // `n` coins of given denominations vector<int> S = { 1, 2, 3 }; int n = S.size(); // total change required int target = 4; // create a map to store solutions to subproblems unordered_map<string, int> lookup; cout << "The total number of ways to get the desired change is " << count(S, n - 1, target, lookup); return 0; } |
Output:
The minimum number of coins required to get the desired change is 4
Java
|
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 59 |
import java.util.HashMap; import java.util.Map; class Main { // Function to find the total number of distinct ways to get a change of `target` // from an unlimited supply of coins in set `S` public static int count(int[] S, int n, int target, Map<String, Integer> lookup) { // if the total is 0, return 1 (solution found) if (target == 0) { return 1; } // return 0 (solution does not exist) if total becomes negative, // no elements are left if (target < 0 || n < 0) { return 0; } // construct a unique map key from dynamic elements of the input String key = n + "|" + target; // if the subproblem is seen for the first time, solve it and // store its result in a map if (!lookup.containsKey(key)) { // Case 1. Include current coin `S[n]` in solution and recur // with remaining change `target-S[n]` with the same number of coins int include = count(S, n, target - S[n], lookup); // Case 2. Exclude current coin `S[n]` from solution and recur // for remaining coins `n-1` int exclude = count(S, n - 1, target, lookup); // assign total ways by including or excluding current coin lookup.put(key, include + exclude); } // return solution to the current subproblem return lookup.get(key); } // Coin Change Problem public static void main(String[] args) { // `n` coins of given denominations int[] S = { 1, 2, 3 }; // total change required int target = 4; // create a map to store solutions to subproblems Map<String, Integer> lookup = new HashMap<>(); System.out.print("The total number of ways to get the desired change is " + count(S, S.length - 1, target, lookup)); } } |
Output:
The minimum number of coins required to get the desired change is 4
Python
|
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 |
# Function to find the total number of distinct ways to get a change of `target` # from an unlimited supply of coins in set `S` def count(S, n, target, lookup): # if the total is 0, return 1 (solution found) if target == 0: return 1 # return 0 (solution does not exist) if total becomes negative, # no elements are left if target < 0 or n < 0: return 0 # construct a unique key from dynamic elements of the input key = (n, target) # if the subproblem is seen for the first time, solve it and # store its result in a dictionary if key not in lookup: # Case 1. Include current coin `S[n]` in solution and recur # with remaining change `target-S[n]` with the same number of coins include = count(S, n, target - S[n], lookup) # Case 2. Exclude current coin `S[n]` from solution and recur # for remaining coins `n-1` exclude = count(S, n - 1, target, lookup) # assign total ways by including or excluding current coin lookup[key] = include + exclude # return solution to the current subproblem return lookup[key] # Coin Change Problem if __name__ == '__main__': S = [1, 2, 3] # `n` coins of given denominations target = 4 # total change required # create a dictionary to store solutions to subproblems lookup = {} print('The total number of ways to get the desired change is', count(S, len(S) - 1, target, lookup)) |
Output:
The minimum number of coins required to get the desired change is 4
The time complexity of the above top-down solution is O(n.target), where n is the total number of coins and target is the total change required. The auxiliary space required by the program is O(n.target).
We can even write a bottom-up version of the above memoized solution. The following code shows how to implement this in C, Java, and Python:
C
|
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 |
#include <stdio.h> // Function to find the total number of distinct ways to get a change of `target` // from an unlimited supply of coins in set `S` int count(int S[], int n, int target) { int T[n + 1][target + 1]; for (int i = 0; i <= n; i++) { for (int j = 0; j <= target; j++) { if (i == 0) { T[0][j] = 0; } else if (j == 0) { T[i][0] = 1; } else if (S[i - 1] > j) { T[i][j] = T[i - 1][j]; } else { T[i][j] = T[i - 1][j] + T[i][j - S[i - 1]]; } } } return T[n][target]; } int main(void) { // `n` coins of given denominations int S[] = { 1, 2, 3 }; int n = sizeof(S) / sizeof(S[0]); // total change required int target = 4; printf("The total number of ways to get the desired change is %d", count(S, n, target)); return 0; } |
Output:
The total number of ways to get the desired change is 4
Java
|
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 |
class Main { // Function to find the total number of distinct ways to get a change of `target` // from an unlimited supply of coins in set `S` public static int count(int[] S, int target) { int n = S.length; int T[][] = new int[n + 1][target + 1]; for (int i = 0; i <= n; i++) { T[i][0] = 1; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= target; j++) { if (S[i - 1] > j) { T[i][j] = T[i - 1][j]; } else { T[i][j] = T[i - 1][j] + T[i][j - S[i - 1]]; } } } return T[n][target]; } public static void main(String[] args) { // `n` coins of given denominations int[] S = { 1, 2, 3 }; // total change required int target = 4; System.out.println("The total number of ways to get the desired change is " + count(S, target)); } } |
Output:
The total number of ways to get the desired change is 4
Python
|
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 |
# Function to find the total number of distinct ways to get a change of `target` # from an unlimited supply of coins in set `S` def count(S, target): n = len(S) T = [[0] * (target + 1) for _ in range(n + 1)] for i in range(n + 1): T[i][0] = 1 for i in range(1, n + 1): for j in range(1, target + 1): if S[i - 1] > j: T[i][j] = T[i - 1][j] else: T[i][j] = T[i - 1][j] + T[i][j - S[i - 1]] return T[n][target] if __name__ == '__main__': # `n` coins of given denominations S = [1, 2, 3] # total change required target = 4 print('The total number of ways to get the desired change is', count(S, target)) |
Output:
The total number of ways to get the desired change is 4
The time and space complexity of the above bottom-up solution remains the same as the memoized recursive solution. However, the space complexity can be reduced to O(target) using the simplified algorithm below:
C
|
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 |
#include <stdio.h> // Function to find the total number of distinct ways to get // a change of `target` from an unlimited supply of coins in set `S` int count(int S[], int n, int target) { int T[target+1]; for (int i = 0; i <= target; i++) { T[i] = 0; } T[0] = 1; for (int i = 0; i < n; i++) { for (int j = S[i]; j <= target; j++) { T[j] += T[j - S[i]]; } } return T[target]; } int main(void) { // `n` coins of given denominations int S[] = { 1, 2, 3 }; int n = sizeof(S) / sizeof(S[0]); // total change required int target = 4; printf("The total number of ways to get the desired change is %d", count(S, n, target)); return 0; } |
Output:
The total number of ways to get the desired change is 4
Java
|
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 |
class Main { // Function to find the total number of distinct ways to get a change of `target` // from an unlimited supply of coins in set `S` public static int count(int[] S, int target) { int T[] = new int[target+1]; T[0] = 1; for (int i = 0; i < S.length; i++) { for (int j = S[i]; j <= target; j++) { T[j] += T[j - S[i]]; } } return T[target]; } public static void main(String[] args) { // `n` coins of given denominations int[] S = { 1, 2, 3 }; // total change required int target = 4; System.out.println("The total number of ways to get the desired change is " + count(S, target)); } } |
Output:
The total number of ways to get the desired change is 4
Python
|
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 |
# Function to find the total number of distinct ways to get # a change of `target` from an unlimited supply of coins in set `S` def count(S, target): T = [0] * (target + 1) T[0] = 1 for i in range(len(S)): j = S[i] while j <= target: T[j] += T[j - S[i]] j = j + 1 return T[target] if __name__ == '__main__': # `n` coins of given denominations S = [1, 2, 3] # total change required target = 4 print('The total number of ways to get the desired change is', count(S, target)) |
Output:
The total number of ways to get the desired change is 4
Exercise: Find the total number of ways to get the desired change from the limited supply of coins of given denominations.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)