Problem Description

You have an array of integers coins that represents different coin denominations and an integer amount that represents a target sum of money.

Your task is to find the number of different combinations of coins that can sum up to exactly the given amount.

Key points about the problem:

• You have an infinite supply of each type of coin (you can use any coin denomination as many times as needed)
• You need to count the number of combinations, not permutations (for example, {1, 2} and {2, 1} count as the same combination)
• If it's impossible to make the target amount with any combination of coins, return 0
• The answer is guaranteed to fit in a 32-bit signed integer

For example:

• If coins = [1, 2, 5] and amount = 5, there are 4 ways to make amount 5:
  • 5 = 5 (one 5-cent coin)
  • 5 = 2 + 2 + 1 (two 2-cent coins and one 1-cent coin)
  • 5 = 2 + 1 + 1 + 1 (one 2-cent coin and three 1-cent coins)
  • 5 = 1 + 1 + 1 + 1 + 1 (five 1-cent coins)

This is a classic coin change combination problem that can be solved using dynamic programming, specifically using the complete knapsack approach where each item (coin) can be used multiple times.

Intuition

To understand how to solve this problem, let's think about it step by step.

Imagine you're trying to make amount j using coins. You have two choices for each coin type:

1. Don't use this coin type at all - then you need to make amount j using only the previous coin types
2. Use at least one of this coin type - then you first use one coin of value x, leaving you with amount j - x to make, which can still use this coin type again (since we have infinite supply)

This leads us to think about dynamic programming. Let's define f[i][j] as the number of ways to make amount j using the first i types of coins.

For each coin type i with value x, we can think about all possible quantities we could use: 0, 1, 2, 3, ... up to k where k * x ≤ j.

This gives us: f[i][j] = f[i-1][j] + f[i-1][j-x] + f[i-1][j-2x] + ... + f[i-1][j-kx]

But there's a clever observation here! If we look at f[i][j-x], it equals: f[i][j-x] = f[i-1][j-x] + f[i-1][j-2x] + ... + f[i-1][j-kx]

Notice that this is exactly the tail part of our first equation! So we can simplify: f[i][j] = f[i-1][j] + f[i][j-x]

This means: the number of ways to make amount j using the first i coins equals:

• The number of ways without using the i-th coin at all: f[i-1][j]
• Plus the number of ways where we use at least one of the i-th coin: f[i][j-x]

The base case is f[0][0] = 1 (one way to make 0 amount using 0 coins: use nothing), and all other f[0][j] = 0 (no way to make positive amount with no coins).

This approach ensures we count combinations, not permutations, because we process coins in a fixed order and decide how many of each type to use, rather than considering different orderings of the same coins.

Learn more about Dynamic Programming patterns.

Solution Approach

Based on our intuition, we implement the dynamic programming solution using a 2D table.

Step 1: Initialize the DP table

We create a 2D array f with dimensions (m+1) × (n+1) where:

• m is the number of coin types
• n is the target amount
• f[i][j] represents the number of ways to make amount j using the first i types of coins

m, n = len(coins), amount
f = [[0] * (n + 1) for _ in range(m + 1)]
f[0][0] = 1  # Base case: one way to make 0 with 0 coins

Step 2: Fill the DP table

We iterate through each coin type and each possible amount:

for i, x in enumerate(coins, 1):  # i goes from 1 to m, x is the coin value
    for j in range(n + 1):         # j goes from 0 to amount
        # First, inherit the ways without using the current coin
        f[i][j] = f[i - 1][j]
      
        # If we can use the current coin (j >= x), add those ways
        if j >= x:
            f[i][j] += f[i][j - x]

The state transition equation we're implementing is:

• f[i][j] = f[i-1][j] + f[i][j-x] when j >= x
• f[i][j] = f[i-1][j] when j < x

How the transition works:

• f[i-1][j]: Ways to make amount j without using the i-th coin at all
• f[i][j-x]: Ways to make amount j-x using coins 1 to i (then add one more coin i to reach j)

Step 3: Return the result

The answer is stored in f[m][n], which represents the number of ways to make the target amount using all available coin types.

return f[m][n]

Time Complexity: O(m × n) where m is the number of coins and n is the amount Space Complexity: O(m × n) for the 2D DP table

This complete knapsack approach ensures we count each unique combination exactly once, as we process coins in order and decide how many of each type to include.

Example Walkthrough

Let's walk through a small example with coins = [1, 2] and amount = 4.

We'll build a DP table where f[i][j] represents the number of ways to make amount j using the first i types of coins.

Step 1: Initialize the table

• Create a 3×5 table (3 rows for 0,1,2 coins; 5 columns for amounts 0,1,2,3,4)
• Set f[0][0] = 1 (one way to make 0 with no coins)

    Amount: 0  1  2  3  4
Coins 0:    1  0  0  0  0
Coins 1:    0  0  0  0  0
Coins 2:    0  0  0  0  0

Step 2: Process coin 1 (value = 1) For each amount j from 0 to 4:

• f[1][0] = f[0][0] = 1 (inherit from above)
• f[1][1] = f[0][1] + f[1][0] = 0 + 1 = 1 (can use one 1-coin)
• f[1][2] = f[0][2] + f[1][1] = 0 + 1 = 1 (use two 1-coins)
• f[1][3] = f[0][3] + f[1][2] = 0 + 1 = 1 (use three 1-coins)
• f[1][4] = f[0][4] + f[1][3] = 0 + 1 = 1 (use four 1-coins)

    Amount: 0  1  2  3  4
Coins 0:    1  0  0  0  0
Coins 1:    1  1  1  1  1
Coins 2:    0  0  0  0  0

Step 3: Process coin 2 (value = 2) For each amount j from 0 to 4:

• f[2][0] = f[1][0] = 1 (inherit from above)
• f[2][1] = f[1][1] = 1 (can't use 2-coin, amount too small)
• f[2][2] = f[1][2] + f[2][0] = 1 + 1 = 2 (either {1,1} or {2})
• f[2][3] = f[1][3] + f[2][1] = 1 + 1 = 2 (either {1,1,1} or {2,1})
• f[2][4] = f[1][4] + f[2][2] = 1 + 2 = 3 (either {1,1,1,1}, {2,1,1}, or {2,2})

    Amount: 0  1  2  3  4
Coins 0:    1  0  0  0  0
Coins 1:    1  1  1  1  1
Coins 2:    1  1  2  2  3

Result: f[2][4] = 3

The three combinations to make 4 are:

1. Four 1-coins: {1,1,1,1}
2. One 2-coin and two 1-coins: {2,1,1}
3. Two 2-coins: {2,2}

Notice how the algorithm naturally avoids counting permutations - we process coins in order and decide how many of each type to use, so {2,1,1} and {1,2,1} are counted as the same combination.

Solution Implementation

Time and Space Complexity

The time complexity of this dynamic programming solution is O(m × n), where m is the number of types of coins and n is the target amount. This is because we have two nested loops: the outer loop iterates through all m coins, and the inner loop iterates through all possible amounts from 0 to n. Each cell f[i][j] is computed exactly once in constant time.

The space complexity is O(m × n). We create a 2D array f with dimensions (m + 1) × (n + 1) to store the number of ways to make each amount using the first i types of coins. Each cell stores a single integer value, resulting in total space usage proportional to m × n.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing Combinations with Permutations

The Pitfall: A common mistake is treating this as a permutation problem, where order matters. For instance, counting {1, 2, 2} and {2, 1, 2} as different ways to make 5.

Why it happens: The instinct might be to iterate through amounts first, then coins:

# WRONG approach - counts permutations
for j in range(1, amount + 1):
    for coin in coins:
        if j >= coin:
            dp[j] += dp[j - coin]

The Solution: Always iterate through coins in the outer loop and amounts in the inner loop. This ensures each combination is counted exactly once:

# CORRECT approach - counts combinations
for coin in coins:
    for j in range(coin, amount + 1):
        dp[j] += dp[j - coin]

2. Incorrect Base Case Initialization

The Pitfall: Forgetting to set dp[0][0] = 1 or incorrectly initializing the entire first row/column.

Why it happens: It's not immediately intuitive that there's exactly one way to make amount 0 (by selecting no coins).

The Solution: Only dp[0][0] should be 1. All other dp[0][j] for j > 0 should remain 0 (there's no way to make a positive amount with zero coins).

3. Space Optimization Without Understanding the Dependencies

The Pitfall: Attempting to optimize from 2D to 1D array incorrectly:

# WRONG - modifying values we still need to read
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
    for j in range(amount + 1):  # Wrong direction!
        if j >= coin:
            dp[j] += dp[j - coin]

The Solution: When optimizing to 1D, iterate through amounts from left to right (not right to left like in 0/1 knapsack):

# CORRECT 1D optimization
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
    for j in range(coin, amount + 1):  # Start from coin value
        dp[j] += dp[j - coin]

4. Index Confusion in 2D Implementation

The Pitfall: Mixing up the coin index with the actual coin value:

# WRONG - using i instead of coins[i-1]
for i in range(1, num_coins + 1):
    for j in range(amount + 1):
        dp[i][j] = dp[i-1][j]
        if j >= i:  # Wrong! Should be j >= coins[i-1]
            dp[i][j] += dp[i][j - i]

The Solution: Always extract the coin value explicitly to avoid confusion:

for i in range(1, num_coins + 1):
    coin_value = coins[i - 1]  # Clear variable name
    for j in range(amount + 1):
        dp[i][j] = dp[i-1][j]
        if j >= coin_value:
            dp[i][j] += dp[i][j - coin_value]