Coin Change II

Medium
91.

Coin Change II

Coin Change II is a medium coding problem on arrays and dynamic programming.

Given distinct coin denominations coins (infinite supply) and a total amount, return the number of combinations that make up that amount (order does not matter). If it cannot be made, return 0.

Example 1

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

Example 2

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

Constraints

  • 1 <= coins.length <= 5
  • 1 <= coins[i] <= 20 (distinct)
  • 0 <= amount <= 60
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function(amount, coins) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Coin Change II — Solution in Python, Java & C++

Coin Change II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Coin Change II is a medium coding problem on arrays and dynamic programming.

  • Difficulty: Medium
  • Topics: Arrays, Dynamic Programming
  • 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

Given distinct coin denominations coins (infinite supply) and a total amount, return the number of combinations that make up that amount (order does not matter). If it cannot be made, return 0.

Example 1

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

Example 2

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

Constraints

  • 1 <= coins.length <= 5
  • 1 <= coins[i] <= 20 (distinct)
  • 0 <= amount <= 60

Hints for Coin Change II

  1. Hint 1

    Loop coins on the OUTSIDE so each combination is counted once.

  2. Hint 2

    dp[a] += dp[a - c] for each coin c.

How to solve Coin Change II

Counting combinations rather than permutations hinges entirely on loop order. Put the coins on the outer loop and the amounts on the inner one: that way each coin is considered once as a whole, so [1,2] and [2,1] are never counted as different answers.

Approach

  1. Create ways[0 .. amount], all zero except ways[0] = 1 — there is exactly one way to make nothing.
  2. For each coin c (outer loop):
  3. Sweep a from c up to amount and add ways[a - c] to ways[a].
  4. Return ways[amount].

Why it works

After processing the first k coins, ways[a] counts the combinations of a using only those coins — so no ordering is ever introduced, because a coin is only ever added to totals already built from coins earlier in the list. Sweeping the amount upwards within a coin is what permits reusing that coin any number of times: ways[a - c] may itself already include copies of c. Swapping the loops would instead count ordered sequences, the answer to a different problem.

Complexity

  • Time — O(amount · coins)
  • Space — O(amount)

Pitfalls

  • Coins outer, amounts inner. Reversing the loops counts permutations and inflates the answer.
  • ways[0] = 1 is the seed that makes everything else non-zero.
  • Sweep the amount upwards (not downwards) — downwards would forbid reusing the coin, solving the 0/1 knapsack instead.
  • An unmakeable amount naturally ends at 0; no sentinel is needed.

Reference solution

Python

from typing import List

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

Java

public static int change(int amount, int[] coins) {
    int[] ways = new int[amount + 1];
    ways[0] = 1;
    for (int c : coins) {
        for (int a = c; a <= amount; a++) ways[a] += ways[a - c];
    }
    return ways[amount];
}

C++

int change(int amount, vector<int>& coins) {
    vector<int> ways(amount + 1, 0);
    ways[0] = 1;
    for (int c : coins) {
        for (int a = c; a <= amount; a++) ways[a] += ways[a - c];
    }
    return ways[amount];
}

JavaScript

var change = function(amount, coins) {
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1;
    for (const c of coins) {
        for (let a = c; a <= amount; a++) dp[a] += dp[a - c];
    }
    return dp[amount];
};

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

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming