Coin Change II — Medium Problem & Solution

You have an infinite supply of each coin in coins. Return the number of combinations that add up to amount.

Difficulty: Medium
Topics: Arrays, Dynamic Programming
Asked at: Amazon, Google, Flipkart
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You have an infinite supply of each coin in coins.

Return the number of combinations that add up to amount. Two combinations differ only by which coins they use and how many of each — order does not matter. Return 0 if the amount cannot be made.

Example 1

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: 5, 2+2+1, 2+1+1+1 and 1+1+1+1+1.

Example 2

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

Example 3

Input: amount = 10, coins = [10]
Output: 1

Constraints

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

How to solve Coin Change II

A one-dimensional knapsack over coin types. Processing one coin at a time and sweeping the amounts upwards counts each multiset exactly once, because a combination is built in a fixed coin order.

Approach

Set dp[0] = 1 — one way to make nothing.
For each coin c, sweep a from c to amount doing dp[a] += dp[a - c].
Return dp[amount].

Why it works

With the coin loop outermost, dp[a] after processing coins 0…i counts the ways to make a using only those coins — and each combination is generated once, in non-decreasing coin index. Swapping the loops would let the same multiset be built in several orders, which counts permutations instead. Sweeping a upwards (rather than downwards) is what allows a coin to be reused.

Complexity

Time — O(n · amount)
Space — O(amount)

Pitfalls

Putting the amount loop outside counts permutations — the answer explodes.
Sweeping a downwards turns it into the 0/1 knapsack, where each coin is used at most once.
dp[0] = 1 is the base case; starting at 0 makes every answer 0.

Reference solution

Python

from typing import List

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

JavaScript

var change = function(amount, coins) {
    var dp = [];
    for (var t = 0; t <= amount; t++) dp.push(0);
    dp[0] = 1;
    for (var i = 0; i < coins.length; i++) {
        for (var a = coins[i]; a <= amount; a++) dp[a] += dp[a - coins[i]];
    }
    return dp[amount];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue