Coin Change II

Problem Description

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.

The answer is guaranteed to fit in a signed 32-bit integer.

Examples

Constraints

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

1D DP: Coin Loop on Outside

Let dp[i] be the number of combinations that make up amount i.

• Initialize dp[0] = 1 (exactly 1 way to make up amount 0: using no coins).
• For each coin coin in coins:
  • For i from coin to amount: dp[i] = dp[i] + dp[i - coin]

Loop Order Matters: By looping over coins on the outside and amount on the inside, we ensure that we build combinations rather than permutations. This means that a combination like [1, 2, 2] is counted once, and we avoid counting duplicate permutations like [2, 1, 2] or [2, 2, 1].

Solution: 1D DP Array

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];
    }
}

class Solution:
    def change(self, amount: int, coins: list[int]) -> int:
        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]

#include <vector>

class Solution {
public:
    int change(int amount, std::vector<int>& coins) {
        std::vector<int> dp(amount + 1, 0);
        dp[0] = 1;

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }

        return dp[amount];
    }
};

Complexity Analysis:

• Time Complexity: O(N * A) where N is the number of coins and A is the amount.
• Space Complexity: O(A) to store the 1D DP array.

← All Problems