MediumBlind75ArrayDP

Coin Change 2

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.

Examples

Input
amount = 5, coins = [1,2,5]
Output
4

There are 4 combinations: 5=5, 5=2+2+1, 5=2+1+1+1, 5=1+1+1+1+1.

Input
amount = 3, coins = [2]
Output
0

There is no combination of coins that sums to 3.

Constraints

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

Approaches

Try all combinations of coins.

CodeT: O(2^n) | S: O(amount)
def change(amount, coins):
    def helper(i, remaining):
        if remaining == 0:
            return 1
        if remaining < 0 or i == len(coins):
            return 0
        return helper(i, remaining - coins[i]) + helper(i + 1, remaining)
    return helper(0, amount)

Use DP where dp[i] is the number of ways to make amount i.

CodeT: O(amount * len(coins)) | S: O(amount)
def change(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]

Same DP with careful iteration order to avoid counting permutations.

Diagram

amount=5, coins=[1,2,5] dp = [1,0,0,0,0,0] coin=1: dp = [1,1,1,1,1,1] coin=2: dp = [1,1,2,2,3,3] coin=5: dp = [1,1,2,2,3,4] Result: 4
CodeT: O(amount * len(coins)) | S: O(amount)
def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for j in range(coin, amount + 1):
            dp[j] += dp[j - coin]
    return dp[amount]

Complexity Comparison

Recursion
T: O(2^n)S: O(amount)

Try all combinations of coins.

DP - Bottom Up
T: O(amount * len(coins))S: O(amount)

Use DP where dp[i] is the number of ways to make amount i.

Optimized DP
T: O(amount * len(coins))S: O(amount)

Same DP with careful iteration order to avoid counting permutations.

Common Mistakes

Counting permutations instead of combinations (wrong iteration order)

Not initializing dp[0] = 1

Using 2D DP when 1D is sufficient

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems