518. Coin Change II

Given coin denominations (unlimited supply of each) and an amount, return the number of combinations that make up that amount. Order does not matter; return 0 if none.

Process one coin type at a time and add its ways into dp[a] += dp[a − coin]. Putting coins in the outer loop counts each combination once, regardless of order.

1function change(amount: number, coins: number[]): number {
2  const dp = new Array(amount + 1).fill(0);
3  dp[0] = 1;
4  for (const c of coins)
5    for (let a = c; a <= amount; a++) dp[a] += dp[a - c];
6  return dp[amount];
7}