Coin Change II (Number of Ways)

Count the number of ways to make a given amount using coins

Language Selection

Choose your preferred programming language

Showing: Python

Problem Statement

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

Input:

  • An array of integers coins representing coin denominations
  • An integer amount representing the target amount

Output:

  • The number of different combinations to make the amount

Constraints:

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

Examples:

Example 1:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: There are 4 ways to make amount 5:
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
Explanation: There is only one way: 10 = 10

Solutions

Approach 1: Bottom-Up Dynamic Programming (Tabulation)

This is the classic unbounded knapsack variation where we count combinations.

Algorithm:

  1. Create dp array where dp[i] = number of ways to make amount i
  2. Initialize dp[0] = 1 (one way to make 0: use no coins)
  3. For each coin, update all amounts that can be made with this coin
  4. Avoid counting permutations by processing coins in outer loop

Python:

def change(amount, coins):
    """
    Bottom-up DP solution for counting combinations
    Time: O(amount * len(coins))
    Space: O(amount)
    """
    dp = [0] * (amount + 1)
    dp[0] = 1  # One way to make amount 0
    
    # Process each coin
    for coin in coins:
        # Update all amounts that can use this coin
        for curr_amount in range(coin, amount + 1):
            dp[curr_amount] += dp[curr_amount - coin]
    
    return dp[amount]

def change_verbose(amount, coins):
    """
    Verbose version with detailed comments
    Time: O(amount * len(coins))
    Space: O(amount)
    """
    # dp[i] represents number of ways to make amount i
    dp = [0] * (amount + 1)
    dp[0] = 1  # Base case: one way to make 0 (use no coins)
    
    # For each coin denomination
    for coin in coins:
        print(f"Processing coin: {coin}")
        # For each amount from coin to target
        for curr_amount in range(coin, amount + 1):
            # Add ways to make (curr_amount - coin) amount
            # using previously processed coins
            dp[curr_amount] += dp[curr_amount - coin]
            print(f"  dp[{curr_amount}] = {dp[curr_amount]}")
    
    return dp[amount]

# Example usage
print(change(5, [1, 2, 5]))  # Output: 4

Java:

class Solution {
    /**
     * Bottom-up DP solution
     * Time: O(amount * coins.length)
     * Space: O(amount)
     */
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;  // Base case
        
        // Process each coin
        for (int coin : coins) {
            // Update all amounts that can use this coin
            for (int currAmount = coin; currAmount <= amount; currAmount++) {
                dp[currAmount] += dp[currAmount - coin];
            }
        }
        
        return dp[amount];
    }
    
    /**
     * Alternative implementation with cleaner variable names
     * Time: O(amount * coins.length)
     * Space: O(amount)
     */
    public int changeAlternative(int amount, int[] coins) {
        int[] ways = new int[amount + 1];
        ways[0] = 1;
        
        for (int coin : coins) {
            for (int sum = coin; sum <= amount; sum++) {
                ways[sum] += ways[sum - coin];
            }
        }
        
        return ways[amount];
    }
}

Go:

// change - Bottom-up DP solution
// Time: O(amount * len(coins))
// Space: O(amount)
func change(amount int, coins []int) int {
    dp := make([]int, amount+1)
    dp[0] = 1  // Base case
    
    // Process each coin
    for _, coin := range coins {
        // Update all amounts that can use this coin
        for currAmount := coin; currAmount <= amount; currAmount++ {
            dp[currAmount] += dp[currAmount-coin]
        }
    }
    
    return dp[amount]
}

JavaScript:

/**
 * Bottom-up DP solution
 * Time: O(amount * coins.length)
 * Space: O(amount)
 */
function change(amount, coins) {
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1;  // Base case
    
    // Process each coin
    for (const coin of coins) {
        // Update all amounts that can use this coin
        for (let currAmount = coin; currAmount <= amount; currAmount++) {
            dp[currAmount] += dp[currAmount - coin];
        }
    }
    
    return dp[amount];
}

C#:

public class Solution {
    /// <summary>
    /// Bottom-up DP solution
    /// Time: O(amount * coins.Length)
    /// Space: O(amount)
    /// </summary>
    public int Change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;  // Base case
        
        // Process each coin
        foreach (int coin in coins) {
            // Update all amounts that can use this coin
            for (int currAmount = coin; currAmount <= amount; currAmount++) {
                dp[currAmount] += dp[currAmount - coin];
            }
        }
        
        return dp[amount];
    }
}

Approach 2: Memoization (Top-Down DP)

Python:

def change_memoization(amount, coins):
    """
    Top-down DP with memoization
    Time: O(amount * len(coins))
    Space: O(amount * len(coins)) - memo table + recursion stack
    """
    memo = {}
    
    def dfs(remaining, coin_index):
        # Base cases
        if remaining == 0:
            return 1
        if remaining < 0 or coin_index >= len(coins):
            return 0
        
        # Check memo
        if (remaining, coin_index) in memo:
            return memo[(remaining, coin_index)]
        
        # Two choices: use current coin or skip it
        use_coin = dfs(remaining - coins[coin_index], coin_index)  # Can reuse same coin
        skip_coin = dfs(remaining, coin_index + 1)  # Move to next coin
        
        memo[(remaining, coin_index)] = use_coin + skip_coin
        return memo[(remaining, coin_index)]
    
    return dfs(amount, 0)

def change_lru_cache(amount, coins):
    """
    Using functools.lru_cache
    Time: O(amount * len(coins))
    Space: O(amount * len(coins))
    """
    from functools import lru_cache
    
    @lru_cache(maxsize=None)
    def dp(remaining, coin_idx):
        if remaining == 0:
            return 1
        if remaining < 0 or coin_idx >= len(coins):
            return 0
        
        return dp(remaining - coins[coin_idx], coin_idx) + dp(remaining, coin_idx + 1)
    
    return dp(amount, 0)

Key Insights

  1. Combinations vs Permutations: Process coins in outer loop to avoid counting permutations
  2. Unbounded Knapsack: Each coin can be used unlimited times
  3. Order of Processing: Coin-first approach ensures we count combinations, not arrangements
  4. Base Case: dp[0] = 1 because there’s one way to make amount 0 (use no coins)
  5. State Transition: ways[amount] = sum of ways[amount - coin] for all valid coins

Edge Cases

  1. amount = 0: Should return 1 (one way: use no coins)
  2. Empty coins array: Should return 0 for any positive amount
  3. Single coin: If coin divides amount evenly, return 1; else 0
  4. Impossible amount: No combination can make the target
  5. Large denominations: Coins larger than target amount

Test Cases

def test_change():
    test_cases = [
        (5, [1, 2, 5], 4),
        (3, [2], 0),
        (10, [10], 1),
        (0, [1, 2, 3], 1),
        (4, [1, 2, 3], 4),  # [1+1+1+1, 1+1+2, 2+2, 1+3]
        (8, [2, 3, 5], 3)   # [2+3+3, 3+5, 2+2+2+2]
    ]
    
    for amount, coins, expected in test_cases:
        result = change(amount, coins)
        assert result == expected, f"amount={amount}, coins={coins}, expected={expected}, got={result}"
        print(f"amount={amount}, coins={coins} -> {result} ✓")

test_change()

Common Mistakes

  1. Wrong order of loops: Processing amount first leads to counting permutations
  2. Base case confusion: Not initializing dp[0] = 1
  3. Index out of bounds: Not checking array boundaries properly
  4. Permutations instead of combinations: Incorrect loop ordering
  5. Negative indexing: Accessing dp with negative indices

Follow-up Questions

  1. Coin Change I: Find minimum coins instead of counting ways
  2. Limited coins: Each coin has a specific quantity
  3. Target sum variations: Different constraints on the target
  4. Space optimization: Can we reduce space complexity?
  5. Path reconstruction: Return actual combinations, not just count
  6. Multiple targets: Handle multiple target amounts efficiently

Interview Tips

  1. Understand the difference: This counts combinations, not permutations
  2. Loop order matters: Coin-first vs amount-first gives different results
  3. Start with examples: Walk through small cases to verify logic
  4. Discuss approaches: Compare top-down vs bottom-up
  5. Handle edge cases: Make sure to test amount = 0 and impossible cases
  6. Explain the recurrence: Clearly state the DP relationship
  7. Space optimization: Mention that this is already space-optimized