Coin Change II

Problem Statement

Given coins and an amount, count how many ways you can make that amount using any number of each coin. This medium-level DP twist is a combinatorics delight—how many coin combos can you craft?

Example

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

Output: 4 (5, 2+2+1, 2+1+1+1, 1+1+1+1+1)

Input: amount = 3, coins = [2]

Output: 0 (no way)

Input: amount = 10, coins = [10]

Output: 1 (10)

Code

public class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}
            

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
    return dp[amount]

# Example usage
print(change(5, [1, 2, 5]))  # 4
print(change(3, [2]))  # 0
            

function change(amount, coins) {
    let dp = new Array(amount + 1).fill(0);
    dp[0] = 1;
    for (let coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
}

// Example usage
console.log(change(5, [1, 2, 5]));  // 4
console.log(change(3, [2]));  // 0
            

Explanation

• DP Insight: dp[i] = number of ways to make amount i.
• Steps: For each coin, add ways using it to all higher amounts.
• Flow Example (5,[1,2,5]): dp[5]=1 (5), +2 (2+1+1+1), +1 (1+1+1+1+1) = 4.
• Why It Works: Accumulates combinations systematically.

Note