Coin Change II

Problem

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.

Example 1:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
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

Constraints:

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

Solution

Approach 1: 2D Dynamic Programming

The key insight is to build up the number of ways to make each amount using each coin type one at a time.

Implementation

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

        # Base case: one way to make amount 0 (use no coins)
        for i in range(n + 1):
            dp[i][0] = 1

        for i in range(1, n + 1):
            for a in range(amount + 1):
                # Don't use current coin
                dp[i][a] = dp[i-1][a]

                # Use current coin (if possible)
                if a >= coins[i-1]:
                    dp[i][a] += dp[i][a - coins[i-1]]

        return dp[n][amount]

Approach 2: Space-Optimized 1D DP

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1  # One way to make 0: use no coins

        # Process each coin type
        for coin in coins:
            # Update ways to make each amount
            for a in range(coin, amount + 1):
                dp[a] += dp[a - coin]

        return dp[amount]

Approach 3: Recursion with Memoization

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        memo = {}

        def dp(i, remaining):
            # Base cases
            if remaining == 0:
                return 1
            if remaining < 0 or i == len(coins):
                return 0

            if (i, remaining) in memo:
                return memo[(i, remaining)]

            # Don't use coin i + use coin i (can reuse)
            result = dp(i + 1, remaining) + dp(i, remaining - coins[i])

            memo[(i, remaining)] = result
            return result

        return dp(0, amount)

Complexity Analysis

2D DP:

Time Complexity: O(n * amount), where n is number of coins.
Space Complexity: O(n * amount) for the 2D dp table.

1D DP:

Time Complexity: O(n * amount).
Space Complexity: O(amount), only one array.

Key Insights

Combinations vs Permutations: We want combinations, not permutations. [1,2] and [2,1] should count as one way.
Order Matters in Implementation: By iterating coins in outer loop and amounts in inner loop, we avoid counting permutations.
Unbounded Knapsack: This is an unbounded knapsack variant - can use each coin unlimited times.
DP Recurrence: dp[i][a] = dp[i-1][a] + dp[i][a-coin]
- Don’t use current coin: dp[i-1][a]
- Use current coin: dp[i][a-coin] (can reuse same coin)
Space Optimization: Since we only need previous row and current row, can use 1D array.
Base Case: There’s one way to make amount 0 - use no coins.
Coin Order Independence: Final answer is same regardless of coin array order since we’re counting combinations.