518. Coin Change II - Explanation

Description

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] <= 5000
0 <= amount <= 5000

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(n * a) time and O(n * a) space, where n is the number of coins and a is the given amount.

Hint 1

As we need to find the total number of combinations, think in terms of recursion and visualize it as a decision tree where multiple coin choices are available at each recursion step. Can you determine a way to allow picking the same coin multiple times? Maybe you should consider the decisions made at each recursion step.

Hint 2

The given coins are unique. We recursively iterate through the coins array using index i, tracking the collected amount along the current path. At each step, we can either skip the current coin or pick it, ensuring the total does not exceed the target. To allow picking the same coin multiple times, we recurse with the same index but an updated amount, generating different combinations.

Hint 3

If we reach the target amount, we return 1. The recursion stops if the index goes out of bounds. We count all possible ways and return the total. This approach is exponential. Can you think of a way to optimize it? Maybe you should consider an approach to avoid redundant computations.

Hint 4

We can use memoization to cache the results of recursive calls and avoid redundant computations. A hash map or a 2D array can be used to store these results.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

Intuition

This problem asks us to find the number of different ways to make up a given amount using unlimited coins of given denominations.

At every step, we make a choice for the current coin:

skip the coin and move to the next one
use the coin and reduce the remaining amount

Recursion is a natural fit here because each choice leads to a smaller subproblem.
The recursive function represents:
“How many ways can we form amount a using coins starting from index i?”

By sorting the coins and always moving forward in the list, we avoid counting the same combination in different orders.

Algorithm

Sort the coin denominations to maintain a consistent order.
Define a recursive function dfs(i, a):
- i is the current coin index
- a is the remaining amount
If the remaining amount a becomes 0:
- Return 1 because a valid combination is formed
If all coins are exhausted (i goes out of bounds):
- Return 0 because no combination can be formed
Initialize a result counter res to 0
If the current coin can be used (a >= coins[i]):
- Option 1: Skip the current coin and move to the next one
- Option 2: Use the current coin and reduce the amount (stay at the same index)
- Add the results of both options to res
Return res as the number of ways for the current state
Start the recursion from coin index 0 with the full amount

class Solution:
    def change(self, 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 & Space Complexity

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

Where $n$ is the number of coins, $a$ is the given amount and $m$ is the minimum value among all the coins.

2. Dynamic Programming (Top-Down)

Intuition

This problem is about counting how many different combinations of coins can make up a given amount, where each coin can be used any number of times.

The pure recursive solution works, but it recomputes the same subproblems again and again. To optimize this, we use top-down dynamic programming (memoization).

Each state is uniquely defined by:

the current coin index i
the remaining amount a

The function answers the question:
“How many ways can we form amount a using coins starting from index i?”

By storing results for each state, we avoid repeated calculations and greatly improve efficiency.

Algorithm

Sort the coin denominations to keep combinations in a fixed order.
Create a 2D memo table memo where:
- memo[i][a] stores the number of ways to form amount a using coins from index i onward
Define a recursive function dfs(i, a):
- i is the current coin index
- a is the remaining amount
If a becomes 0:
- Return 1 since a valid combination is formed
If all coins are exhausted (i is out of bounds):
- Return 0 because no combination can be formed
If the current state is already computed in memo:
- Return the stored value
Initialize the result res to 0
If the current coin can be used (a >= coins[i]):
- Option 1: Skip the current coin and move to the next one
- Option 2: Use the current coin and reduce the amount (stay at the same index)
- Add both results to res
Store res in memo[i][a]
Start the recursion from index 0 with the full amount
Return the final result

class Solution:
    def change(self, 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 & Space Complexity

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

Where $n$ is the number of coins and $a$ is the given amount.

3. Dynamic Programming (Bottom-Up)

Intuition

This problem asks for the number of different ways to make up a given amount using unlimited coins, where order does not matter.

Instead of using recursion, we can solve this using bottom-up dynamic programming, where we build the answer step by step using a table.

The key idea is to define a state that represents:

how many ways we can form a certain amount
using coins starting from a particular index

By filling the DP table from the base cases upward, we ensure that all required subproblems are already solved when needed.

Algorithm

Sort the coin denominations to maintain a consistent order and avoid duplicate combinations.
Let n be the number of coins.
Create a 2D DP table dp of size (n + 1) x (amount + 1):
- dp[i][a] represents the number of ways to form amount a using coins from index i onward
Initialize the base case:
- For any i, set dp[i][0] = 1 since there is exactly one way to make amount 0 (choose no coins)
Iterate through the coins in reverse order:
For each coin index i and for each amount a from 0 to amount:
- If the current coin can be used (a >= coins[i]):
  - Option 1: Skip the current coin -> dp[i + 1][a]
  - Option 2: Use the current coin -> dp[i][a - coins[i]]
  - Add both options to get dp[i][a]
After filling the table, the answer is stored in dp[0][amount]
Return dp[0][amount]

class Solution:
    def change(self, 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 & Space Complexity

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

Where $n$ is the number of coins and $a$ is the given amount.

4. Dynamic Programming (Space Optimized)

Intuition

This problem asks for the number of different combinations of coins that can make up a given amount, where each coin can be used unlimited times and the order of coins does not matter.

In the bottom-up dynamic programming approach, we used a 2D table to store results for each coin index and amount. However, each row only depends on:

the row below it (skipping the coin)
the current row itself (using the same coin)

Because of this, we can optimize the space and store only one 1D array at a time, updating it carefully to preserve correctness.

Algorithm

Create a 1D array dp of size amount + 1:
- dp[a] represents the number of ways to form amount a using coins processed so far
Initialize dp[0] = 1 since there is exactly one way to form amount 0
Iterate through the coins in reverse order:
For each coin:
- Create a new array nextDP to store updated results
- Set nextDP[0] = 1 as the base case
For each amount a from 1 to amount:
- First copy the value from dp[a] (skipping the current coin)
- If the current coin can be used (a - coins[i] >= 0):
  - Add nextDP[a - coins[i]] (using the current coin again)
Replace dp with nextDP after processing the current coin
After all coins are processed, dp[amount] contains the total number of combinations
Return dp[amount]

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

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

Time & Space Complexity

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

Where $n$ is the number of coins and $a$ is the given amount.

5. Dynamic Programming (Optimal)

Intuition

We need to count how many different combinations of coins can make up a given amount, where:

each coin can be used unlimited times
the order of coins does not matter

From earlier dynamic programming approaches, we observe that for each coin, the number of ways to form an amount only depends on:

the number of ways to form the same amount without using the coin
the number of ways to form a smaller amount using the current coin

Because of this, we can use a single 1D DP array and update it in place, achieving the most space-efficient solution.

The DP array always represents the number of ways to form each amount using the coins processed so far.

Algorithm

Create a 1D array dp of size amount + 1:
- dp[a] represents the number of ways to form amount a
Initialize dp[0] = 1 since there is exactly one way to form amount 0
Iterate through the coins in reverse order:
For each coin, iterate through all amounts from 1 to amount:
- If the current coin value is less than or equal to the amount:
  - Add dp[a - coin] to dp[a]
After processing all coins, dp[amount] holds the total number of combinations
Return dp[amount]

class Solution:
    def change(self, 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 & Space Complexity

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

Where $n$ is the number of coins and $a$ is the given amount.

Common Pitfalls

Counting Permutations Instead of Combinations

Iterating over amounts in the outer loop and coins in the inner loop counts permutations (order matters), not combinations. This causes [1,2] and [2,1] to be counted as different ways.

# Wrong: Counts permutations
for a in range(1, amount + 1):
    for coin in coins:
        dp[a] += dp[a - coin]

# Correct: Counts combinations (coins in outer loop)
for coin in coins:
    for a in range(coin, amount + 1):
        dp[a] += dp[a - coin]

Forgetting the Base Case

Not initializing dp[0] = 1 means there is no way to build any amount. The base case represents the one valid way to make amount 0: use no coins.

Allowing Negative Array Access

When checking dp[a - coins[i]], failing to verify a >= coins[i] first causes negative index access or runtime errors.

# Wrong: Can access negative index
dp[a] += dp[a - coins[i]]

# Correct: Check before accessing
if a >= coins[i]:
    dp[a] += dp[a - coins[i]]