Coin Change II

Medium
869.

Coin Change II

Coin Change II is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google and Flipkart interviews.

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.
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, asked in Amazon, Google and Flipkart interviews.

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.

Hints for Coin Change II

  1. Hint 1

    Count combinations, not permutations — 1+2 and 2+1 are the same.

  2. Hint 2

    Put the coin loop outside and the amount loop inside; that fixes an order on the coins and stops permutations being counted.

  3. Hint 3

    dp[a] is the number of ways to make a using the coins considered so far.

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

  1. Set dp[0] = 1 — one way to make nothing.
  2. For each coin c, sweep a from c to amount doing dp[a] += dp[a - c].
  3. 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]

Java

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

C++

int change(int amount, vector<int>& coins) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1;
    for (int c : coins) {
        for (int a = c; a <= amount; a++) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming