518. Coin Change 2

At a Glance

Topic: dp-2d
Pattern: Dynamic Programming (unbounded knapsack: count ways)
Difficulty: Medium
Companies: Google, Facebook, Microsoft, Amazon, Apple
Frequency: High
LeetCode: 518

Given amount and distinct positive coins (infinite use each), return the number of combinations that sum to amount. Order of coins in a combination does not matter (1+2 and 2+1 count once). Input: amount, coins. Output: count.

Recognition Cues

“Number of combinations” to make amount
“Order does not matter” → process coins in fixed outer loop
Unbounded use → inner loop on sums ascending

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — enumerate integer partitions — exponential.
Better — 2D ways[coinIndex][sum] — O(coins * amount) time.
Optimal — 1D ways[sum] with coin-outer loop — O(coins * amount) time / O(amount) space. <- pick this in interview.

Optimal Solution

Go

package main

func changeTable(amount int, coins []int) int {
	ways := make([][]int, len(coins)+1)
	for index := range ways {
		ways[index] = make([]int, amount+1)
		ways[index][0] = 1
	}
	for coinIndex := 1; coinIndex <= len(coins); coinIndex++ {
		coin := coins[coinIndex-1]
		for sum := 0; sum <= amount; sum++ {
			without := ways[coinIndex-1][sum]
			with := 0
			if sum >= coin {
				with = ways[coinIndex][sum-coin]
			}
			ways[coinIndex][sum] = without + with
		}
	}
	return ways[len(coins)][amount]
}

func change(amount int, coins []int) int {
	ways := make([]int, amount+1)
	ways[0] = 1
	for _, coin := range coins {
		for sum := coin; sum <= amount; sum++ {
			ways[sum] += ways[sum-coin]
		}
	}
	return ways[amount]
}

JavaScript

function changeTable(amount, coins) {
	const numCoins = coins.length;
	const ways = Array.from({ length: numCoins + 1 }, () =>
		new Array(amount + 1).fill(0)
	);
	for (let index = 0; index <= numCoins; index++) {
		ways[index][0] = 1;
	}
	for (let coinIndex = 1; coinIndex <= numCoins; coinIndex++) {
		const coin = coins[coinIndex - 1];
		for (let sum = 0; sum <= amount; sum++) {
			const without = ways[coinIndex - 1][sum];
			const withCoin = sum >= coin ? ways[coinIndex][sum - coin] : 0;
			ways[coinIndex][sum] = without + withCoin;
		}
	}
	return ways[numCoins][amount];
}

function change(amount, coins) {
	const ways = new Array(amount + 1).fill(0);
	ways[0] = 1;
	for (const coin of coins) {
		for (let sum = coin; sum <= amount; sum++) {
			ways[sum] += ways[sum - coin];
		}
	}
	return ways[amount];
}