Coin Change II
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
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.