Coin Change II

Return different ways to make change

Coin Change II

Problem Statement

You are given an integer array, coins, representing coins of different denominations, and an integer, amount, representing a total amount of money.

Your goal is to find the total number of combinations that make up that amount.

• You can assume you have an infinite number of each type of coin.
• If the amount of money cannot be made up by any combination of the coins, return 0.
• The final answer is guaranteed to fit into a signed 32-bit 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

The Core Idea: Total Ways vs. Minimum Coins

The main difference between this problem and the standard "Coin Change" problem is the objective:

• In standard Coin Change, we want the minimum number of coins. So, we use Math.min(take, notTake) and add 1 to our coin count when we take a coin.
• In Coin Change II, we want the total possible ways to make the change. Instead of finding a minimum, we simply add the successful combinations from both our choices: take + notTake.

For our base case at the first coin (index === 0), if the remaining amount is perfectly divisible by the coin's value, it counts as exactly 1 valid combination. If it is not divisible, it counts as 0 valid combinations.

Memoization (Top-Down Approach)

We evaluate each coin starting from the last index. For every coin, we can either:

• Skip (notTake): Move to the previous coin while keeping the required amount the same.
• Pick (take): Subtract the coin's value from the amount. We stay at the same index because we have an infinite supply of the current coin.

We add the results of both branches to get the total number of ways for that state, storing the result in our dp array to avoid recalculating it.

var change = function (amount, coins) {
    if (amount === 0) return 1;
    if (coins.length === 0) return 0;

    let dp = Array.from(
        { length: coins.length },
        () => Array(amount + 1).fill(-1)
    );

    function recurr(index, value) {
        // If the exact amount is reached, this is 1 valid combination
        if (value === 0) {
            return 1;
        }

        // Base case: check if the remaining value is divisible by the first coin
        if (index === 0) {
            return value % coins[0] === 0 ? 1 : 0;
        }

        if (dp[index][value] !== -1) {
            return dp[index][value];
        }

        let notTake = recurr(index - 1, value);
        let take = 0;

        // Only take the coin if it doesn't exceed the required value
        if (coins[index] <= value) {
            take = recurr(index, value - coins[index]);
        }

        // Total ways is the sum of both choices
        dp[index][value] = take + notTake;

        return dp[index][value];
    }

    return recurr(coins.length - 1, amount);
};

Tabulation (Bottom-Up Approach)

We can translate the recursive logic into an iterative table setup. dp[i][value] represents the number of combinations that make up value using a subset of coins up to index i.

We start by filling the first row (the base case) for the very first coin, marking 1 for any target amount that is perfectly divisible by that coin. Then, we iterate through the rest of the coins and amounts, summing the take and notTake values.

var change = function (amount, coins) {
    let dp = Array.from({ length: coins.length }, () => Array(amount + 1).fill(0));

    // Fill the base case row for the very first coin
    for (let target = 0; target <= amount; target++) {
        if (target % coins[0] === 0) {
            dp[0][target] = 1;
        }
    }

    // Fill the rest of the DP table
    for (let i = 1; i < coins.length; i++) {
        for (let value = 0; value <= amount; value++) {
            
            let notTake = dp[i - 1][value];
            let take = 0;

            if (coins[i] <= value) {
                // Add the number of ways to form the remaining value using the current coin subset
                take = dp[i][value - coins[i]];
            }

            dp[i][value] = take + notTake;
        }
    }

    return dp[coins.length - 1][amount];
};