Coin Change Combination Problem

Sample Example 

Let's understand the problem statement better with an example.

Input:

Denominations = {1, 2, 5}
amount = 11

Output:
11

Explanation : 

There are a total of 11 ways to make 11 using a combination of these coins.

A few combinations are : 

(2, 2, 2, 5) 

(1, 5, 5) 

(1, 2, 2, 2, 2, 2) 

(1, 1, 1, 2, 2, 2, 2) 

(1, 1, 1, 2, 2, 2, 2) 

(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1) 

Brute Force Algorithm

The naive (or brute force) generates all possible combinations of coins with multiple instances of each and checks whether their sum is equal to the amount.

The base case would be that if the amount is 0, the only possible way would be 1 i.e., not selecting any coin. If the denomination array is empty and the amount is non-zero, then we can never form the given amount, hence the max number of ways for this would be 0. 

For all other cases, every coin in the denomination array would have 2 choices i.e. to get selected or not. 

Algorithm

The brute force algorithm for the coin change combination problem can be summarized in the following points:

1. Define a function named coinCombinations that takes three arguments:
   • a vector of integers representing the available denominations of coins
   • an integer representing the index of the current denomination being considered
   • an integer representing the target amount of money to make change for
   • In the coinCombinations function, define a base case for when the target amount of money is 0. In this case, return 1 to indicate that a combination has been found.
2. Initialize a variable named ways to 0, which will keep track of the total number of combinations.
3. Use a for loop to iterate over the available denominations of coins, starting at the current index idx.
4. Within the loop, check if the current denomination can be used to make change for the remaining target amount of money. If so, recursively call the coinCombinations function with the same denominations vector, the current index as the new starting index, and the target amount of money reduced by the value of the current denomination.
5. Add the result of the recursive call to the ways variable.
6. After the loop is finished, return the final value of ways.
7. In the main function, call the coinCombinations function with the given parameters and store the result in a variable named ways.
8. Print the number of coin change combinations found by the algorithm in the form of variable ways

Note that this algorithm has an exponential time complexity, as it considers all possible combinations of denominations. For large denominations and target amounts, it may take a long time to run.

Dry Run

Lets have look in the dry run and how recursive function calls are working

The main function calls the coinCombinations function with the following parameters:

1. denominations = {1, 2, 5}
2. idx = 0
3. target = 11

Then starts the recursive call.

• coinCombinations( idx = 0 , target = 11 ) 
  • coinCombinations( idx = 0 , target = 10 ) 
    • coinCombinations( idx = 0 , target = 9 ) 
      • coinCombinations( idx = 0 , target = 8 ) 
        • coinCombinations( idx = 0 , target = 7 ) 
          Likewise it goes till target = 0 and we return 1.
• coinCombinations( idx = 1 , target = 9 ) 
  • coinCombinations( idx = 1 , target = 7 ) 
  • coinCombinations( idx = 2 , target = 4 ) 
• coinCombinations( idx = 2 , target = 6 ) 
  • coinCombinations( idx = 2 , target = 1 ) , return as target 1 is smaller than coin[2] = 5.

Likewise each recursive subproblem reaches to its base case.

Implementation in Java 

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        int n = 3;
        List<Integer> denominations = Arrays.asList(1, 2, 5);
        int target = 11;
        int ways = coinCombinations(denominations, 0, target);
        System.out.print("Coin change combinations are: ");
        System.out.println(ways);
    }
    
    // Recursive approach
    public static int coinCombinations(List<Integer> denominations , int idx, int target){
        // Base Case
        if (target == 0) return 1;
        int ways = 0;
        for (int i = idx; i < denominations.size(); i++){
            // Counting ways if i-th denomination cam be included
            if (target - denominations.get(i) >=0 )
                ways += coinCombinations(denominations, i, target-denominations.get(i));
        }
        return ways;
    }
}

 

Output

Implementation in C++ 

#include <iostream>
#include <vector>
using namespace std;

int coinCombinations(vector<int>& denominations, int idx, int target) {
    // Base Case
    if (target == 0) return 1;
    int ways = 0;
    for (int i = idx; i < denominations.size(); i++) {
        // Counting ways if i-th denomination can be included
        if (target - denominations[i] >= 0)
            ways += coinCombinations(denominations, i, target - denominations[i]);
    }
    return ways;
}


int main() {
    int n = 3;
    vector<int> denominations{1,2,5};
    int target = 11;
    
    int ways = coinCombinations(denominations, 0, target);
    cout << "Coin change combinations are: " << ways << endl;

    return 0;
}

Output

Time Complexity

The time complexity of the brute force algorithm for the coin change combination problem is O(((target / m) + 1) ^ N) where the target is the target amount, m is the denomination of a coin/value of a coin, and N is the Number of coins. As for each coin we have (target/m) + 1 option (target/m times we can take this coin and plus 1 if we are not taking this coin) and we have N such coins. Therefore overall time complexity becomes O(((target / m) + 1) ^ N).

Space Complexity

The space complexity is O(target) as the height of the recursion tree can go up to the target only.

Using Top Down Dp

We could optimize the time complexity of our previous approach by maintaining a dp array where dp[i] stores the total possible ways for each amount (i.e. 1 to a given amount). For Eg, dp[5] means the total number of ways to amount 5 can be paid using the given coins where each coin can be used multiple times.

Let's look at the recursive tree:

At every moment we make two decisions, 

i) Choose the current coin (represented as the first element of the list). This condition terminates when the amount is less than the coin value.

ii) Leave the current coin, and move to the next coin. This condition terminates when no further coin remains.

Since the recursive approach had a lot of overlapping subproblems, dp array would help us avoid that repetitive work.

Algorithm 

Here's the algorithm for the coin change combination problem using memoization with recursion:

1. Define a function called coinCombinations that takes a vector of integers called denominations, an integer called idx, an integer called target, and a vector of vectors of integers called dp as parameters. The function returns an integer.
2. Check the base cases:
   1. If the target is 0, return 1 as there is one way to make change with zero coins.
   2. If the index is equal to the size of the denominations vector or the target is less than 0, return 0 as there are no ways to make change.
3. Look up in the dp array if the current index and target have already been computed. If so, return the value stored in the dp array.
4. If the current coin can be picked, recursively call the coinCombinations function by picking the current coin and subtracting its value from the target, and keeping the current index the same.
5. If the current coin cannot be picked, recursively call the coinCombinations function by not picking the current coin and incrementing the index by 1.
6. Return the sum of the values obtained from steps 4 and 5.
7. Store the result obtained from step 6 in the dp array at the current index and target.
8. Define the main function:
9. Declare and initialize an integer variable n to 3, a vector of integers called denominations to {1, 2, 5}, and an integer called target to 11.
10. Declare a vector of vectors of integers called dp with dimensions n x (target + 1) and initialize all elements to -1.
11. Call the coinCombinations function with the denominations vector, index 0, target, and dp array as parameters, and store the result in an integer variable called ways.
12. Print the value of ways to the console which is a return coin combination.

Dry Run

The program starts executing from the main() function.

1. Initialize an integer variable n to 3, a vector of integers named denominations to {1, 2, 5}, and an integer variable target to 11.
2. Create a 2D vector dp of size n x (target + 1) and initialize all its values to 0.
3. Call the coinCombinations() function with arguments denominations, 0, target, and dp.
4. Let's see what a recursion tree looks like.

• coinCombinations( idx = 0 , target = 11 ) 
  • coinCombinations( idx = 0 , target = 10 ) | Pick
    • coinCombinations( idx = 0 , target = 9) | Pick
      • coinCombinations( idx = 0 , target = 8 ) | Pick
      • coinCombinations( idx = 1 , target = 9 ) | nonPick
    • coinCombinations( idx = 0 , target = 10 ) | nonPick
  • coinCombinations( idx = 1 , target = 11 ) | nonPick
    • coinCombinations( idx = 1 , target = 9 ) | Pick
    • coinCombinations( idx = 2 , target = 11 ) | nonPick

You can see that we have overlapping subproblems which can be memoized and then returned if already visited. The above diagram of recursion also shows the overlapping subproblems represented in blue color. 

Implementation in Java 

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        int n = 3;
        List<Integer> denominations = Arrays.asList(1, 2, 5);
        int target = 11;

        // Forming Dp Array
        int[][] dp = new int[denominations.size()][target + 1]; 
        for(int i=0; i<denominations.size(); i++){
            for(int j = 0; j<=target; j++){
                dp[i][j] = -1;
            }
        }
        int ways = coinCombinations(denominations, 0, target, dp);
        System.out.print("Coin change combinations are: ");
        System.out.println(ways);
    }
    
    // Top Down DP approach
      public static int coinCombinations(List<Integer> denominations, int idx, int target, int[][] dp) {
        // Base Case
        if (target == 0) return 1;
        if (idx == denominations.size() || target < 0) return 0;
        
        // LookUp in Dp Array
        if (dp[idx][target] != -1) return dp[idx][target];

        // Pick current coin
        int pick = coinCombinations(denominations, idx, target - denominations.get(idx), dp);

        // Do not pick current coin
        int nonPick = coinCombinations(denominations, idx + 1, target, dp);

        return dp[idx][target] = pick + nonPick;
    }
}

Output

Implementation in C++

#include <iostream>
#include <vector>
using namespace std;

int coinCombinations(vector<int>& denominations, int idx, int target, vector<vector<int>>& dp) {
    // Base Case
    if (target == 0) return 1;
    if (idx == denominations.size() || target < 0) return 0;

    // LookUp in Dp Array
    if (dp[idx][target] != -1) return dp[idx][target];

    // Pick current coin
    int pick = coinCombinations(denominations, idx, target - denominations[idx], dp);

    // Do not pick current coin
    int nonPick = coinCombinations(denominations, idx + 1, target, dp);

    return dp[idx][target] = pick + nonPick;
}

int main() {
    int n = 3;
    vector<int> denominations{1,2,5};
    int target = 11;
    
    // Forming Dp Array
    vector<vector<int>> dp(n, vector<int>(target + 1, -1));
    int ways = coinCombinations(denominations, 0, target, dp);
    cout << "Coin change combinations are: " << ways << endl;
    return 0;
}

Output

Time Complexity

The time complexity of the coin change combination problem with memoization is O(N * target), where n is the number of coin denominations. This is because we only compute the result for each unique combination of (idx, target) once, and future calls to the same state simply look up the previously computed value in the dp array.

Space Complexity

The space complexity of the memoization approach is also O(n * target), since we are storing the previously computed results in a 2D dp array. This can potentially take up a lot of space, especially if the target amount is very large. However, in practice, the dp array will only store a small fraction of all possible combinations, since we only need to compute values for reachable target amounts.

Using Bottom-Up Dp

In this approach, we will implement the above DP logic in an iterative manner.

Algorithm

1. Initialize a 1D dp array of size target + 1 with all elements set to 0, except for dp[0], which is set to 1.
2. For each coin denomination, iterate through the dp array starting from index denominations[i].
3. For each index j, update the value of dp[j] by adding dp[j - denominations[i]], but only if j - denominations[i] is greater than or equal to 0.
4. Essentially, for each coin denomination, we are computing the number of ways to reach each possible target amount j by either not including the current coin denomination or including it once, twice, three times, etc.
5. At the end, the value of dp[target] represents the total number of coin change combinations that can be used to obtain the target amount.

Implementation in Java 

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        int n = 3;
        int[] denominations = {1, 2, 5};
        int target = 11;
        
        coinCombinationsDp(denominations, target);
    }
    
    // Bottom Up DP approach
    public static void coinCombinationsDp(int[] denominations, int target){
        // Forming dp array
        int[] dp = new int[target + 1];
        // 0 amount could be get in 1 way (i.e. not selecting any coin)
        dp[0] = 1;
        
        // Counting coin change combinations
        for (int i = 0; i < denominations.length; i++){
            for (int j = 1; j < dp.length; j++){
                if (j - denominations[i] < 0) continue;
                dp[j] += dp[j- denominations[i]];
            }
        }
        
        System.out.print("Coin change combinations are: ");
        System.out.println(dp[dp.length - 1]);
    }
}

Output

Implementation in C++

#include<bits/stdc++.h>
using namespace std;

// Bottom Up DP approach
void coinCombinationsDp(vector<int>& denominations, int target) {  
    // Forming dp array
    vector<int> dp(target + 1, 0);
    // 0 amount could be get in 1 way (i.e. not selecting any coin)
    dp[0] = 1;
    
    // Counting coin change combinations
    for (int i = 0; i < denominations.size(); i++){
        for (int j = 1; j < dp.size(); j++){
            if (j - denominations[i] < 0) continue;
            dp[j] += dp[j - denominations[i]];
        }
    }
    cout << "Coin change combinations are: " << dp[dp.size() - 1] << endl;
}

int main() {
    int n = 3;
    vector<int> denominations{1, 2, 5};
    int target = 11;
    
    coinCombinationsDp(denominations, target);
    return 0;
}

Output

Time Complexity

The time complexity of the bottom-up dynamic programming approach for the coin change problem is O(N * target), where N is the number of denominations. 

Space Complexity

The space complexity is O(target), as we are using an array dp of size target.

Check out Longest Common Substring

Frequently Asked Questions

What is dynamic programming?

Dynamic programming is both a mathematical optimization method and a computer programming method mainly used to optimize plain recursion.  

What are two ways to apply dynamic programming?

The two ways to apply dp are bottom-up (i.e., iterative way) and top-down (i.e., using dp in recursion, commonly known as memoization).

What is the combination and how is it different from permutation?

In permutations, we can consider numbers in the array in any order but while forming a combination, numbers could be considered only in forward order.

Why are we optimizing using dp?

This is because the recursive approach had a lot of overlapping subproblems, the dp array would help us avoid that repetitive work.

What is the dynamic programming approach to solve the Coin Change Problem?

The dynamic programming approach involves breaking down the problem into smaller subproblems and using previously calculated solutions for small problems to efficiently solve the larger problem.

Conclusion

In this blog, we learned various approaches to the Coin Change Combination. Coin Change Combination is a standard recursive problem that is optimized via dp. The optimized time complexity of this problem is O(n * amount) which uses a bottom-up DP approach.

Check out more blogs on different dp problems like LCS, and Friends Pairing Problems to read more about these topics in detail. If you want to enhance more, then check out our blogs.

• LCS
• Friends Pairing Problem
• Minimum Number Of Coins
• C Programming

 

And many more on our platform Coding Ninjas Studio.

Refer to our Guided Path to upskill yourself in DSA, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundles for placement preparations.

However, you may consider our paid courses to give your career an edge over others!

Happy Learning!