Coin Change II

Medium

Problem

Given coin denominations (unlimited supply) and an amount, return the number of combinations that make up the amount. Order does not matter: 1+2 and 2+1 are the same combination.

Example 1

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

5; 2+2+1; 2+1+1+1; 1+1+1+1+1.

Test cases

Case 1

Input:    5, [1,2,5]
Expected: 4

Case 2

Input:    3, [2]
Expected: 0

Case 3

Input:    10, [10]
Expected: 1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Unbounded knapsack, coins in the outer loop

Time O(amount × coins)Space O(amount)

dp[a] = ways to make a. Looping coins outside counts combinations (each order once); looping amounts outside would count permutations.

function change(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];
}

The loop order is the whole trick — be ready to explain it.