Coin Change II

Problem Statement

This challenge involves determining the total number of unique combinations of coins that equal a specific monetary amount. You are provided with an integer array coins, where each element represents the denomination of a coin. You are also given an integer amount, which is the total value you need to achieve through various combinations of the coins provided. Importantly, it's assumed you have access to an infinite supply of each coin denomination.

The main goal here is to calculate the number of possible ways to reach the exact amount using any combination of the coins in the array. If no combination of the given coins can achieve the specified amount, the function should return 0. The result should always fit within a 32-bit signed integer.

Examples

Example 1

Input:

amount = 5, coins = [1,2,5]

Output:

4

Explanation:

there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2

Input:

amount = 3, coins = [2]

Output:

0

Explanation:

the amount of 3 cannot be made up just with coins of 2.

Example 3

Input:

amount = 10, coins = [10]

Output:

1

Constraints

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• All the values of coins are unique.
• 0 <= amount <= 5000

Approach and Intuition

To solve this problem, one can utilize dynamic programming due to its ability to break down complex problems into simpler, overlapping subproblems. Here's a step-wise intuition and approach:

1. Create a dynamic programming array (dp) where the index represents a monetary amount, and the value at each index represents the number of ways to create that amount using the available coins. Initialize the array with zeros, and set dp[0] = 1 since there's one way to create the amount of zero—that is using no coins (an important base case).

2. Iterate over each coin in the coins array. For each coin, update the dp array:

   • Start from the value of the coin to the desired amount (inclusive). For each intermediate amount i, update dp[i] by adding the value of dp[i - current coin] to it. This addition reflects the number of ways to make the amount i given that current coin is used.

3. To further elaborate step 2, suppose you are processing the coin of value coin.

   • For each amount from coin to amount, the number of new combinations that can include this coin is equal to the combinations that result in the amount amount - coin.

4. The final value at dp[amount] after processing all coins will give you the total number of combinations to form amount with the provided denominations.

By following the above dynamic programming approach, each amount from 1 to amount considers contributions from all accessible coin operations, effectively building up the total count of combinations by leveraging calculated results of prior amounts. This method is efficient due to its polynomial time complexity relative to the number and value of coins and the maximum amount desired.

Solutions

class Solution {
public:
    int countWays(int total, vector<int>& denom) {
        int count = denom.size();
        vector<unsigned long long> ways(total + 1);
        ways[0] = 1;  // Base case initialization
    
        for (int idx = count - 1; idx >= 0; idx--) {
            for (int sum = denom[idx]; sum <= total; sum++) {
                ways[sum] += ways[sum - denom[idx]]; // Update the number of ways to form sum
            }
        }
    
        return ways[total] <= INT_MAX ? ways[total] : -1; // Handle overflow scenarios
    }
};