Coin Change II

How it works

We need to count how many different combinations of coins can make up a given amount, where:

• each coin can be used unlimited times
• the order of coins does not matter

From earlier dynamic programming approaches, we observe that for each coin, the number of ways to form an amount only depends on:

• the number of ways to form the same amount without using the coin
• the number of ways to form a smaller amount using the current coin

Because of this, we can use a single 1D DP array and update it in place, achieving the most space-efficient solution.

The DP array always represents the number of ways to form each amount using the coins processed so far.

Steps

1. Create a 1D array dp of size amount + 1:
   • dp[a] represents the number of ways to form amount a
2. Initialize dp[0] = 1 since there is exactly one way to form amount 0
3. Iterate through the coins in reverse order:
4. For each coin, iterate through all amounts from 1 to amount:
   • If the current coin value is less than or equal to the amount:
     • Add dp[a - coin] to dp[a]
5. After processing all coins, dp[amount] holds the total number of combinations
6. Return dp[amount]

Complexity

• Time complexity: O(n * a)
• Space complexity: O(a)

Where n is the number of coins and a is the given amount.

Things to watch for

Counting Permutations Instead of Combinations

Iterating over amounts in the outer loop and coins in the inner loop counts permutations (order matters), not combinations. This causes [1,2] and [2,1] to be counted as different ways.

Forgetting the Base Case

Not initializing dp[0] = 1 means there is no way to build any amount. The base case represents the one valid way to make amount 0: use no coins.

Allowing Negative Array Access

When checking dp[a - coins[i]], failing to verify a >= coins[i] first causes negative index access or runtime errors.

from typing import List

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for i in range(len(coins) - 1, -1, -1):
            for a in range(1, amount + 1):
                dp[a] += dp[a - coins[i]] if coins[i] <= a else 0
        return dp[amount]

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<uint> dp(amount + 1, 0);
        dp[0] = 1;
        for (int i = coins.size() - 1; i >= 0; i--) {
            for (int a = 1; a <= amount; a++) {
                dp[a] = dp[a] + (coins[i] <= a ? dp[a - coins[i]] : 0);
            }
        }
        return dp[amount];
    }
};