Coin Change II

Problem Statement

You are given an integer array coins representing coins of different denominations (e.g. 1 dollar, 5 dollars, etc) and an integer amount representing a target amount of money.

Return the number of distinct combinations that total up to amount. If it’s impossible to make up the amount, return 0.

You may assume that you have an unlimited number of each coin and that each value in coins is unique.

Example 1:

# Input: amount = 4, coins = [1,2,3]
# Output: 4

Explanation:

1+1+1+1 = 4
1+1+2 = 4
2+2 = 4
1+3 = 4

Example 2:

# Input: amount = 7, coins = [2,4]
# Output: 0

Constraints:

1 <= coins.length <= 100
1 <= coins[i] <= 1000
0 <= amount <= 1000

Recommended Time and Space Complexity

You should aim for a solution with O(n * a) time and O(a) space, where n is the number of coins and a is the target amount.

Hint 1

Consider using dynamic programming to solve this problem.

Hint 2

You can build a table dp where dp[i][j] represents the number of distinct combinations to make up amount j using the first i coins.

Hint 3

The base case is dp[0][0] = 1 (one way to make up amount 0 using no coins).

Hint 4

For each coin and amount, you can either include the coin or exclude it. If you include the coin, you subtract its value from the amount and look up the result in the table. If you exclude the coin, you simply look up the result in the table without using the coin.

Solution

Recursion

def change_recursive(amount: int, coins: List[int]) -> int:
    coins.sort()

    def dfs(i, a):
        if a == 0:
            return 1
        if i >= len(coins):
            return 0

        res = 0
        if a >= coins[i]:
            res = dfs(i + 1, a)
            res += dfs(i, a - coins[i])
        return res

    return dfs(0, amount)

Time complexity: O(2 ^ {max(n, \frac{a}{m})}) Space complexity: O(max(n, \frac{a}{m}))

Dynamic Programming (Top-Down)

def change_dp_top_down(amount: int, coins: List[int]) -> int:
    coins.sort()
    memo = [[-1] * (amount + 1) for _ in range(len(coins) + 1)]

    def dfs(i, a):
        if a == 0:
            return 1
        if i >= len(coins):
            return 0
        if memo[i][a] != -1:
            return memo[i][a]

        res = 0
        if a >= coins[i]:
            res = dfs(i + 1, a)
            res += dfs(i, a - coins[i])

        memo[i][a] = res
        return res

    return dfs(0, amount)

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

Dynamic Programming (Bottom-Up)

def change_dp_bottom_up(amount: int, coins: List[int]) -> int:
    n = len(coins)
    coins.sort()
    dp = [[0] * (amount + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][0] = 1

    for i in range(n - 1, -1, -1):
        for a in range(amount + 1):
            if a >= coins[i]:
                dp[i][a] = dp[i + 1][a]
                dp[i][a] += dp[i][a - coins[i]]

    return dp[0][amount]

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

Dynamic Programming (Space Optimized)

def change_dp_space_optimized(amount: int, coins: List[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1
    for i in range(len(coins) - 1, -1, -1):
        next_dp = [0] * (amount + 1)
        next_dp[0] = 1

        for a in range(1, amount + 1):
            next_dp[a] = dp[a]
            if a - coins[i] >= 0:
                next_dp[a] += next_dp[a - coins[i]]
        dp = next_dp
    return dp[amount]

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

Dynamic Programming (Optimal)

def change_dp_optimal(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]

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