Coin Change II

Medium0/1 Knapsack (DP)NeetCode 150MidOpen on LeetCodeUpdated Nov 11, 2026

You're given an integer amount and an array of distinct coin denominations. Return how many different combinations of coins add up to amount, with an unlimited supply of each coin. Combinations that use the same coins in a different order count once. If amount is 0, the empty combination counts, so the answer is 1.

Examples

amount = 6, coins = [1,3] returns 3

The combinations are six 1s, one 3 with three 1s, and two 3s.

amount = 7, coins = [2,4] returns 0

Every combination of 2s and 4s is even, so 7 can't be made.

amount = 0, coins = [5] returns 1

Using no coins at all is the one way to make 0.

Constraints

1 <= coins.length <= 300
1 <= coins[i] <= 5000
All coins are distinct.
0 <= amount <= 5000
The answer fits in a 32-bit signed integer.

Hints

Hint 1

Counting combinations means order must not matter. How can you force every combination to be built in one canonical order?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

This is an unbounded knapsack count. Let dp[a] be the number of combinations that make a, with dp[0] = 1. Process the coins one at a time, and for each coin sweep a from coin up to amount, adding dp[a - coin] to dp[a]. Because each coin is fully processed before the next one starts, every combination is built in one fixed coin order and counted exactly once. Sweeping upward lets a coin be reused. O(amount * coins) time, O(amount) space.

Time

O(amount * n)

Space

O(amount)

Pitfall

Putting the amount loop outside the coin loop. That counts ordered sequences, so 1 + 3 and 3 + 1 are counted separately, which is the answer to Combination Sum IV.

Solutions

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int a = coin; a <= amount; a++) {
                dp[a] += dp[a - coin];
            }
        }
        return dp[amount];
    }
}

class Solution:
    def change(self, amount: int, coins) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for a in range(coin, amount + 1):
                dp[a] += dp[a - coin]
        return dp[amount]