Coin Change II

Problem Description

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.

Naive Solution (Brute Force with Recursion)

A straightforward approach is to use recursion. For each coin, we can either include it or exclude it. If we include it, we reduce the amount by the coin's value and recursively call the function. If we exclude it, we move on to the next coin. This continues until the amount becomes 0 (we found a valid combination) or less than 0 (invalid combination) or we run out of coins.

Code (Python)

def change_recursive(amount, coins):
    def solve(index, current_amount):
        if current_amount == 0:
            return 1
        if current_amount < 0 or index >= len(coins):
            return 0

        include = solve(index, current_amount - coins[index])
        exclude = solve(index + 1, current_amount)
        return include + exclude

    return solve(0, amount)

Big O Analysis:

• Time Complexity: O(2ⁿ), where n is the number of coins because in the worst case, each coin can be either taken or not taken, resulting in exponential branching.
• Space Complexity: O(n), due to the depth of the recursion stack.

Optimal Solution (Dynamic Programming)

A more efficient approach is to use dynamic programming. We create a DP table dp where dp[i] stores the number of ways to make the amount i. We initialize dp[0] to 1 because there is one way to make an amount of 0 (using no coins).

Then, for each coin, we iterate through the dp table from the coin's value up to the total amount. For each amount i, we add the number of ways to make i - coin to dp[i]. This is because we can either use the current coin or not use it.

Code (Python)

def change_dp(amount, coins):
    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]

Big O Analysis:

• Time Complexity: O(n * amount), where n is the number of coins and amount is the target amount. We iterate through all coins and for each coin, we iterate up to the amount.
• Space Complexity: O(amount), for the DP table.

Edge Cases:

• Amount is 0: Return 1, as there's one way to make zero amount (no coins).
• Coins array is empty: If the amount is 0, return 1. Otherwise return 0, as no coins can be used.
• Amount is negative: This is not possible based on the problem constraints, but generally you would return 0.
• No combination is possible: The algorithm will correctly return 0 in this case as dp[amount] will remain 0.

Summary

The optimal dynamic programming solution provides a significant improvement in time complexity over the naive recursive approach, making it suitable for larger amounts and more coin denominations.