Coin Change II Problem (C++, Java, Python)

Money is the most essential thing that we deal with every day. Isn’t it interesting that we have so many denominations of money and can use them in different combinations to pay a certain amount? In this article, we will explore one very famous dynamic programming-based problem: Coin Change II. We will explore different solutions, from the brute force approach to the most optimal one.

Coin Change II Problem Statement

In the Coin Change II problem, we are given different denominations of money, like 1, 2, 5, 10, etc. We are given a total amount we need to form using combinations of these coins. We need to find the total number of possible combinations.

Let’s understand it better with an example:

Input:

coins: [ 1, 2, 3 ]
amount: 5

Output:

Explanation:

The 5 different possible combinations are:

5 = 3 + 2

5 = 3 + 1 + 1

5 = 2 + 2 + 1

5 = 2 + 1 + 1 + 1

5 = 1 + 1 + 1 + 1 + 1

Brute Force Approach: Using Recursion

The most basic solution is to find all the possible combinations and add the ones where the sum is equal to the amount. We can use recursion to explore all the possible combinations. The following steps need to be followed:

We will iterate over the coin array, and at each index, we have two options to either take that coin or ignore that coin.
Take a variable index, which we will use to iterate over the coins array, and initialize it to 0.
Write a recursive function such that, if we take the current coin, we will subtract its value from the total amount; else if we ignore it, the amount will remain the same.
The base case of the recursion will be if we have left with amount = 0, i.e., the combination is found, we can simply return 1 to add it to the answer, else if the coins array is traversed completely, return 0.
If we can take this coin, subtract the amount, and call for the remaining amount by passing the same index, we can infinitely take a coin.
If we skip this coin, increment the index and call the function again for the same amount.
Add the answer returned from both the recursion calls, and return it.

The time complexity for this solution will be O(2^(n*amount)) since we are exploring all the combinations using recursion.

Memoization Approach

We can improve the time complexity of the recursive solution by using the concept of memoization. We can make use of dynamic programming to store the results and reuse them for overlapping problems. If we have calculated the possible combinations of a certain amount, we do not need to calculate again whenever we get the same amount remaining.

Dynamic programming can be applied through these easy steps:

Write the same recursive function and use the below steps to apply memoization to it.
Create a 2d dp array of size n x ( amount + 1 ) to store the results of the sub-problems.
Initialize the dp array to -1; as for the combinations not possible the answer will be -1.
Before calculating again for a certain amount, we will first check it in our dp array ( dp[index][amount] ); if we have calculated it before, we can simply use it.
Else, calculate the answer and set dp[index][amount] = answer, so that we can use it again for the sub-problems.

The time complexity for this solution will be O(n * amount), where n is the number of coins. There are at max n * amount number of possible combinations, so if we explore them all, the time complexity will be O(n*amount).

Tabulation Approach

The tabulation approach is nothing but a bottom-up version of the above memoization approach. Earlier we were starting from index 0 and amount. Now, we will begin with the amount as 0 and try to reach the solution.

The following steps are required to be followed in the solution:

Create a 2d dp array with size n x ( amount + 1 ).
If amount = 0, there is only one possible combination, so initialize dp[0][0] as 1.
Use a loop from 1 to n to iterate over the row of the dp array and find the solution for each index.
Use a nested loop to iterate over the amount, i.e., from 0 to amount.
If we take a current coin, add the dp[i][amount – coins[i-1]] since the value of that coin gets subtracted from the amount.
Otherwise, if we didn’t take that coin, we can simply add dp[i-1][amount].
Return the dp[n][amount], which contains the total number of possible combinations that can make the sum = amount

The time complexity for this solution will be O(n * amount), where n is the number of coins. We are using two nested loops, one from 1 to n and the other from 0 to amount. That’s why time complexity is O(n*amount).

Optimal Approach: Tabulation + Space Optimization

As we have seen in the above approaches, we have significantly reduced the time complexity, but space is still an issue for us. To reduce the space complexity, we need to optimize our tabulation solution.

We can observe that the answer for any sub-problem depends on two things, dp[i-1][amount] and dp[i][amount – coins[i] ], i.e., our answer depends on just the current and previous row. S,o instead of storing answers for each point, we can store just the current and previous rows. This will eventually bring the complexity down to O(2*amount).

The following modifications are needed to be done in the tabulation solution:

Use two arrays, i.e., current and previous of size = ( amount + 1 ), instead of a 2d dp array.
The current[amount – coins[i]] represents our dp[i][amount – coins[I] ], and the previous[amount] represents our dp[i-1][amount].
Initialize the current vector inside the loop 0 to amount so that we can calculate its values for each amount.
Update the previous = current once the calculations are performed, as the current row becomes the previous when we move to the next row.
Finally, return the answer as the previous[amount], which is nothing but equal to dp[n][amount].

Let’s take our example and understand the steps:

Initialize the current and previous vectors:

Iteration: 1 Index = 1

Iteration: 2 Index = 2

The answer is previous[amount], i.e. 5

C++ Code

Here is the C++ Solution for the Coin Change II Problem:

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

int main() {
    // Input
    vector<int> coins = {1, 2, 3};
    int amount = 5;
    int n = coins.size(); 

    // Initialize the previous vector
    vector<long> previous(amount + 1, 0);

    // Initialize base condition
    for (int i = 0; i <= amount; i++) {
        if (i % coins[0] == 0)
            previous[i] = 1;
    }

    for (int i = 1; i < n; i++) {
        // Initialize the current vector
        vector<long> current(amount + 1, 0);
        
        for (int targetAmount = 0; targetAmount <= amount; targetAmount++) {
            // If we ignore the current coin
            long ans1 = previous[targetAmount]; 
            
            // If we take the current coin
            long ans2 = 0;
            if (coins[i] <= targetAmount)
                ans2 = current[targetAmount - coins[i]];
        
            // Answer will be sum of both        
            current[targetAmount] = ans1 + ans2;
        }
        
        // Since current row now become previous
        previous = current;
    }

    cout << "Number of possible combinations are: " << previous[amount];
    return 0;
}

Java Code

Let’s implement it in Java:

import java.util.Arrays;

public class CoinChange {
    public static void main(String[] args) {
        // Input
        int[] coins = {1, 2, 3};
        int amount = 5;
        int n = coins.length;

        // Initialize the previous array
        long[] previous = new long[amount + 1];
        Arrays.fill(previous, 0);
        
        // Initialize base condition
        for (int i = 0; i <= amount; i++) {
            if (i % coins[0] == 0)
                previous[i] = 1;
        }

        // Loop through each coin
        for (int i = 1; i < n; i++) {
            // Initialize the current array
            long[] current = new long[amount + 1];
            Arrays.fill(current, 0);

            // Loop through each possible amount
            for (int targetAmount = 0; targetAmount <= amount; targetAmount++) {
                // If we ignore the current coin
                long ans1 = previous[targetAmount];
                
                // If we take the current coin
                long ans2 = 0;
                if (coins[i] <= targetAmount)
                    ans2 = current[targetAmount - coins[i]];
                
                // Answer will be sum of both
                current[targetAmount] = ans1 + ans2;
            }

            // Update previous array with current array
            previous = current;
        }

        System.out.println("Number of possible combinations are: " + previous[amount]);
    }
}

Python Code

Here is the Python code for the Coin Change II Problem:

def main():
    # Input
    coins = [1, 2, 3]
    amount = 5
    n = len(coins)

    # Initialize the previous array
    previous = [0] * (amount + 1)
    for i in range(amount + 1):
        if i % coins[0] == 0:
            previous[i] = 1

    # Loop through each coin
    for i in range(1, n):
        # Initialize the current array
        current = [0] * (amount + 1)

        # Loop through each possible amount
        for target_amount in range(amount + 1):
            # If we ignore the current coin
            ans1 = previous[target_amount]
            
            # If we take the current coin
            ans2 = 0
            if coins[i] <= target_amount:
                ans2 = current[target_amount - coins[i]]
            
            # Answer will be sum of both
            current[target_amount] = ans1 + ans2

        # Update previous array with current array
        previous = current

    print("Number of possible combinations are:", previous[amount])


if __name__ == "__main__":
    main()

Output:

Number of possible combinations are: 5

The space complexity is O(amount), which is used by the previous and current arrays.

Conclusion

So, we explore one of the problems involving recursion and dynamic programming. We understood all the approaches to solve the problem of Coin Change II. We were able to reduce the time complexity from exponential to O(n*amount).