Code Implementation

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] += dp[x - coin]
        return dp[amount]
      

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

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

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

Problem Description

You are given an integer amount and an array coins representing different coin denominations. Your task is to determine the number of unique ways to make up the value amount using any number of coins from coins. Each coin can be used an unlimited number of times, but the order of coins does not matter (combinations, not permutations).

• Return the total number of distinct combinations that sum up to amount.
• If no combination can make up the amount, return 0.
• All coin denominations are positive integers and there are no duplicate denominations.

Thought Process

At first glance, this problem resembles the classic "coin change" problem, but instead of finding the minimum number of coins, we are counting all possible combinations that sum up to the target amount. A brute-force approach would be to try every possible way to pick coins and count those that sum up to the target. However, this quickly becomes infeasible as the amount and number of coins increase, due to the exponential number of possibilities.

To optimize, we recognize that this is a variation of the "Unbounded Knapsack" problem, where each coin can be used unlimited times. We need a way to systematically count combinations without repeating work. Dynamic Programming (DP) is a natural fit, as it allows us to build up solutions to smaller subproblems and avoid redundant calculations. The key insight is to count combinations (not permutations), so the order in which coins are chosen does not matter.

Solution Approach

We use a 1-dimensional dynamic programming array dp of size amount + 1, where dp[x] represents the number of ways to make up amount x using the available coins.

1. Initialization: Set dp[0] = 1. There is one way to make amount 0: use no coins.
2. Iterate over each coin: For each coin, iterate through all amounts from coin up to amount.
   • For each x, update dp[x] by adding dp[x - coin]. This means: the number of ways to make x increases by the number of ways to make x - coin (by adding this coin).
3. Final Answer: After processing all coins, dp[amount] contains the total number of combinations.

This approach avoids overcounting by ensuring that for each coin, we only consider combinations that include it or not, and always process coins in a fixed order.

Example Walkthrough

Suppose amount = 5 and coins = [1, 2, 5].

1. Start: dp = [1, 0, 0, 0, 0, 0] (only dp[0]=1)
2. Process coin 1:
   • For each x from 1 to 5: dp[x] += dp[x - 1]
   • Result: dp = [1, 1, 1, 1, 1, 1]
3. Process coin 2:
   • For x=2: dp[2] += dp[0] → 1+1=2
   • For x=3: dp[3] += dp[1] → 1+1=2
   • For x=4: dp[4] += dp[2] → 1+2=3
   • For x=5: dp[5] += dp[3] → 1+2=3
   • Result: dp = [1, 1, 2, 2, 3, 3]
4. Process coin 5:
   • For x=5: dp[5] += dp[0] → 3+1=4
   • Result: dp = [1, 1, 2, 2, 3, 4]
5. Final answer: dp[5] = 4

The four combinations are: [1,1,1,1,1], [1,1,1,2], [1,2,2], [5].

Time and Space Complexity

• Brute-force: Exponential time, as we would try every possible combination of coins. For n coins and target amount, the complexity is O(amount^n).
• Optimized DP:
  • Time Complexity: O(amount × n), where n is the number of coin types. We process each coin for each amount.
  • Space Complexity: O(amount) for the dp array.

The optimized approach is efficient and scales well for reasonable input sizes.

Summary

The Coin Change II problem is a classic example of dynamic programming, where we count the number of ways to reach a target sum using unlimited coins of given denominations. By carefully structuring our DP array and iterating coins in order, we efficiently compute the answer while avoiding overcounting. The 1D DP solution is both elegant and practical, turning an exponential brute-force problem into a linear one in terms of amount and number of coins.