Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Count the number of distinct combinations (not permutations) of unlimited-supply coins that sum to a target amount. Use dp[x] = ways to make x, seed dp[0] = 1, and loop coins on the OUTSIDE, amount on the inside: for each coin, for x from coin to amount, dp[x] += dp[x - coin]. The outer-coin loop is what makes {1,2} and {2,1} count once. O(coins × amount) time, O(amount) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can express make-change as an unbounded-knapsack count AND whether you understand that loop order is what distinguishes combinations from permutations.
Where candidates slip
Putting amount on the outside and coins on the inside, which counts permutations and massively overcounts (e.g. reports {1,2} and {2,1} as two ways).
How to stand out
Explain the loop-order rule explicitly, justify dp[0] = 1 as 'one way to make nothing', and contrast this counting DP with the minimum-coins DP it's often confused with.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCounting ways to make an amountDoes order matter?No (this problem)YesExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 3
Brute Force — Recurse on Take-Coin / Skip-Coin
1Hint 1Explore hintHide hint
Fix a starting coin index. From there you can either use the current coin again (subtract it, stay on the same index) or move on to the next coin index permanently. What does each path count toward?
2Hint 2Explore hintHide hint
Define count(i, rem) = ways to make rem using coins from index i onward. count(i, rem) = count(i, rem - coins[i]) + count(i + 1, rem).
3Hint 3Explore hintHide hint
Base cases: rem == 0 → 1 (a valid combination), rem < 0 or i past the end → 0. Staying on index i is what allows unlimited reuse; only ever moving forward is what avoids counting reorderings.
A · Core idea
Model the count as a sequence of decisions over coin indices. Standing at coin index i with rem left to make, you either:
- 1Use coin `i` again — subtract
coins[i]fromremand stay at indexi(unlimited supply lets you reuse it), or - 2Move past coin `i` — advance to index
i + 1, never to return.
The total is the sum of both branches. Hitting rem == 0 means you've formed one valid combination (return 1); rem < 0 or running off the end of the coins means dead end (return 0).
Why staying on `i` is correct for unlimited supply. Because coins are reusable, after spending one coin of value coins[i] you may want another of the same value, so you don't advance the index on a 'use'. You only advance when you decide to stop using coin i.
Why we never go back to a smaller index. This is the combination-vs-permutation guard at the recursion level. Once you move past coin i, you can't return to it. That forces every combination to be built in a fixed coin-index order — say, all 1s decided before any 2s — so {1,2} is generated exactly once, never also as {2,1}. If you allowed revisiting earlier indices, you'd count every ordering separately.
Why we don't ship this. The same (i, rem) pair is reached through many decision paths, so it's recomputed exponentially often. For amount = 10⁴ this is hopeless. But there are only coins.length × (amount + 1) distinct (i, rem) states — the cue to cache them.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
amount = 4, coins = [1, 2, 3]Interactive diagram
Decision tree branches use-again vs advance
count(0, 4)Left edges reuse the current coin; right edges advance the index. Leaves at rem=0 are valid combinations.
4C · Code with teaching comments
Reference implementation previewpublic long countWays(int amount, int[] coins) { return count(coins, 0, amount); } private long count(int[] coins, int i, int rem) {Explore the full codeHide the full code
D · Why it works and complexityO(2^(amount/min)) exponential timeO(amount) spaceOpen the invariant and proofExplore the proofHide the proof
The 'stay on index i vs advance' structure is the unbounded-knapsack signature. Never moving to a smaller index is the recursion-level equivalent of the coins-outer loop — both impose a canonical order that prevents counting permutations.
ComplexityO(2^(amount/min)) exponential time, O(amount) space — Each call branches two ways (use current coin / advance), and the tree depth grows with amount/min(coin), giving exponential time. Recursion depth is O(amount) on the call stack.
E · Edge cases and pitfalls3Advancing the index on a 'use' — forbids reusing a coin, breaking unlimited supply.Explore edge casesHide edge cases
Pitfalls
- Advancing the index on a 'use' — forbids reusing a coin, breaking unlimited supply.
- Allowing recursion back to a smaller index — counts permutations instead of combinations.
- Running it for amount = 10⁴ — exponential time never returns; memoize or tabulate.
Approach 2 of 3
Top-Down Memoization (Java) vs 2D Tabulation (Python)
1Hint 1Explore hintHide hint
There are only coins.length × (amount + 1) distinct (i, rem) states. Cache each one.
2Hint 2Explore hintHide hint
Top-down: memoize count(i, rem) in a 2D array. Bottom-up: build dp[i][x] = ways to make x using the first i coin types.
3Hint 3Explore hintHide hint
Tabulation recurrence: dp[i][x] = dp[i-1][x] (don't use coin i) + dp[i][x - coins[i-1]] (use coin i, stay on row i). dp[i][0] = 1 for every i.
A · Core idea
Same recurrence as the brute force, now with each (i, rem) state solved a single time — shown top-down in Java and bottom-up in Python.
Java — top-down memoization. Keep the recursion but store results in a Long[][] memo indexed by (i, rem). A null entry means 'not computed'; on a cache hit return immediately. The exponential tree collapses to one evaluation per state.
Python — bottom-up 2D tabulation. Build a table dp[i][x] = number of ways to make x using only the first i coin types. The recurrence at cell (i, x) is:
dp[i-1][x]— ways that don't use coiniat all, plusdp[i][x - coins[i-1]]— ways that use at least one coini; we stay on rowibecause the supply is unlimited.
Seed dp[i][0] = 1 for all i (one way to make 0: take nothing). The answer is dp[coins.length][amount].
Why the 2D table makes the combination rule obvious. Row i only ever looks at row i-1 (skip coin i) or earlier columns of the same row i (use coin i). It never looks at a later coin's row. So coin i is fully considered before coin i+1 enters the picture — the table literally fixes the coin order, which is exactly why each combination is counted once. This is the structural reason the 1D version puts coins on the outer loop.
Where the two styles diverge. Top-down recursion consumes call-stack depth proportional to amount. In Python this bites — the default recursion limit (~1000) overflows for amount = 10⁴, so Python is written bottom-up with plain loops. Java handles the recursion depth comfortably. Same time and space either way; the choice is about stack safety, not asymptotics.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
amount = 4, coins = [1, 2, 3]Array state
row 0
no coins: only make 0
4C · Code with teaching comments
Reference implementation previewpublic long countWays(int amount, int[] coins) { Long[][] memo = new Long[coins.length + 1][amount + 1]; return count(coins, 0, amount, memo); } Explore the full codeHide the full code
D · Why it works and complexityO(coins × amount) timeO(coins × amount) spaceOpen the invariant and proofExplore the proofHide the proof
Memoization and tabulation solve the identical state set — lazily vs eagerly. The 2D tabulation also doubles as a proof: because a cell reads only the previous coin's row and earlier columns of its own row, the coin ordering is enforced automatically, guaranteeing combinations. That insight is what lets you safely compress to one row.
ComplexityO(coins × amount) time, O(coins × amount) space — Each of the coins × (amount + 1) states is computed once with O(1) work → O(coins × amount) time. The 2D cache holds that many entries → O(coins × amount) space.
E · Edge cases and pitfalls3In Java, using long[][] for the memo can't distinguish 'unset' from a real 0 — use Long[][] with null.Explore edge casesHide edge cases
Pitfalls
- In Java, using long[][] for the memo can't distinguish 'unset' from a real 0 — use Long[][] with null.
- In Python, a top-down version overflows the recursion limit at amount = 10⁴ — tabulate.
- Forgetting dp[i][0] = 1 for every row — the base case must seed each prefix of coins.
Approach 3 of 3 · Optimal
1D Rolling Array — Coins Outer (Optimal)
1Hint 1Explore hintHide hint
In the 2D table, row i only reads row i-1 (same column) and row i (earlier columns). Can you overwrite a single row in place instead of keeping all rows?
2Hint 2Explore hintHide hint
Keep one array dp of size amount+1, dp[0] = 1. For each coin, sweep x from coin to amount and do dp[x] += dp[x - coin].
3Hint 3Explore hintHide hint
The coin loop MUST be the outer one. Each coin is fully absorbed before the next begins, which is what counts combinations. Sweeping x forward (not backward) gives the unlimited-supply reuse.
A · Core idea
Collapse the 2D table to one row. Maintain dp of length amount + 1 with dp[0] = 1. For each coin, sweep x from coin up to amount, accumulating dp[x] += dp[x - coin].
Why one array suffices. In the 2D recurrence, dp[i][x] reads dp[i-1][x] (the value already sitting in dp[x] before this coin's pass) and dp[i][x - coin] (a value already updated in this same pass, since x - coin < x and we sweep forward). So a single in-place array carries both pieces of information — the old row in untouched cells, the new row in cells already swept.
Why coins must be the outer loop. This is the heart of the problem. With coins outside, the entire contribution of coin c is folded in before coin c+1 is ever considered. Every combination is therefore built in one fixed coin order — all the 1s chosen conceptually before the 2s, and so on — so {1,1,2} is produced exactly once. Flip the loops (amount outside, coins inside) and at each amount you reconsider every coin, generating {1,2} and {2,1} as separate paths — that counts permutations, the classic overcount bug. Same three lines, swapped loops, different problem.
Why the inner loop goes forward. Sweeping x upward lets dp[x - coin] already include uses of the current coin, so a coin can be used many times — unlimited supply. If you swept backward, dp[x - coin] would still hold the pre-coin value, allowing each coin at most once: that's exactly 0/1 knapsack. The direction of the inner loop silently switches between unlimited and single-use.
Why we ship this. Same O(coins × amount) time as the table but O(amount) space, and a tiny, hard-to-misremember loop nest. State the loop-order rule aloud and the interviewer knows you understand why it works, not just that it does.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
amount = 4, coins = [1, 2, 3]Array state
init
dp[0] = 1
4C · Code with teaching comments
D · Why it works and complexityO(coins × amount) timeO(amount) spaceOpen the invariant and proofExplore the proofHide the proof
Two orthogonal loop decisions encode two independent properties: outer loop (coins vs amount) chooses combinations vs permutations; inner-loop direction (forward vs backward) chooses unlimited vs single-use. Master those two switches and the entire knapsack-counting family collapses into one four-line template.
ComplexityO(coins × amount) time, O(amount) space — Two nested loops — coins.length on the outside, amount on the inside — with O(1) work per cell → O(coins × amount) time. A single dp array of length amount+1 → O(amount) space.
E · Edge cases and pitfalls6amount = 0, coins = [1, 2] — Loops update nothing for x ≥ coin only; dp[0] stays 1 → returns 1, the empty combination.Explore edge casesHide edge cases
Edge cases handled
amount = 0, coins = [1, 2]Loops update nothing for x ≥ coin only; dp[0] stays 1 → returns 1, the empty combination.amount = 3, coins = [2]coin 2 sweeps x=2,3: dp[2]+=dp[0]=1, dp[3]+=dp[1]=0 → dp[3]=0. Odd target unreachable.amount = 5, coins = [5]dp[5] += dp[0] = 1 → returns 1. A single coin equal to the amount is one combination.
Pitfalls
- Swapping the loops (amount outer, coins inner) — counts permutations and overcounts badly.
- Sweeping the inner loop backward — turns unlimited supply into 0/1 knapsack (each coin once).
- Forgetting dp[0] = 1 — every count collapses to 0 because nothing seeds the recurrence.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic long countWays(int amount, int[] coins) { long[] dp = new long[amount + 1]; dp[0] = 1; for (int coin : coins) { for (int x = coin; x <= amount; x++) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Loops swapped — counting permutations
With amount outside and coins inside, each amount reconsiders every coin, so {1,2} and {2,1} are both counted. On amount=4, coins=[1,2,3] this reports far more than 4.
Explore the code comparisonHide the code comparison
Loops swapped — counting permutations
With amount outside and coins inside, each amount reconsiders every coin, so {1,2} and {2,1} are both counted. On amount=4, coins=[1,2,3] this reports far more than 4.
Don't write this
for x in range(1, amount + 1): # amount OUTER
for coin in coins:
if x >= coin:
dp[x] += dp[x - coin] # counts permutationsWrite this instead
for coin in coins: # coins OUTER
for x in range(coin, amount + 1):
dp[x] += dp[x - coin] # counts combinations2Backward inner loop — wrong supply model
Sweeping x downward leaves dp[x-coin] at its pre-coin value, so each coin is used at most once — that solves 0/1 knapsack, not unlimited make-change.
Explore the code comparisonHide the code comparison
Backward inner loop — wrong supply model
Sweeping x downward leaves dp[x-coin] at its pre-coin value, so each coin is used at most once — that solves 0/1 knapsack, not unlimited make-change.
Don't write this
for (int coin : coins)
for (int x = amount; x >= coin; x--) // backward → 0/1 knapsack
dp[x] += dp[x - coin];Write this instead
for (int coin : coins)
for (int x = coin; x <= amount; x++) // forward → unlimited supply
dp[x] += dp[x - coin];3Missing dp[0] = 1 base case
dp[x - coin] bottoms out at dp[0]. If dp[0] is 0, no combination ever registers and every dp[x] stays 0.
Explore the code comparisonHide the code comparison
Missing dp[0] = 1 base case
dp[x - coin] bottoms out at dp[0]. If dp[0] is 0, no combination ever registers and every dp[x] stays 0.
Don't write this
dp = [0] * (amount + 1)
# dp[0] left at 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] += dp[x - coin]Write this instead
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for x in range(coin, amount + 1):
dp[x] += dp[x - coin]Revise
Carry the pattern into the interview
Pattern to remember
Unbounded knapsack — counting combinations
Code pattern to memorize
dp = [0]*(amount+1); dp[0] = 1
for coin in coins: # coins OUTSIDE
for x in range(coin, amount+1):
dp[x] += dp[x - coin]
return dp[amount]Rules to remember
- 1Loop coins outside, amount inside → counts combinations (order ignored). Swap them and you count permutations — the single most important detail.
- 2Seed
dp[0] = 1: there is exactly one way to make amount 0 — use no coins. This base case feeds every other value. - 3Inner loop runs
xfromcoinupward (not downward) because each coin has unlimited supply — you may reuse it within the same pass. - 4Iterate the inner loop forward; a backward inner loop would turn this into 0/1 knapsack (each coin used at most once).
- 5Answer is
dp[amount]. If it's 0, the amount is unreachable with the given coins.
Use this pattern when
- Count ways to reach a target using items with unlimited supply
- Combinations where order does NOT matter (a multiset of coins)
- Partition / make-change / stamp problems with reusable denominations
- Any unbounded-knapsack counting variant
Choose another pattern when
- Order matters (sequences, not multisets) → amount outside, coins inside (permutation count, Combination Sum IV)
- Each item used at most once → 0/1 knapsack, inner loop goes backward
- Minimise the NUMBER of coins, not count ways → different DP (min over dp[x-coin]+1)
- Need the actual coin sets, not a count → backtracking, not this DP
Interview takeaway
Loop order encodes whether order matters. Coins-outside counts combinations; amount-outside counts permutations. Internalise that one rule and the whole unbounded-knapsack family — make change, Combination Sum IV, perfect squares — falls out of the same template.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical unbounded-knapsack counting DP. Coins on the outer loop + forward inner loop = count combinations with unlimited supply. Flip the outer loop for permutations (Combination Sum IV); reverse the inner loop for 0/1 knapsack. Same template as Perfect Squares and partition counting.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Coin Change IIComing soonThe identical counting problem on LeetCode — coins outer, amount inner.
- Coin ChangeMinimise the NUMBER of coins instead of counting ways — dp[x] = min(dp[x], dp[x-coin]+1).
- Combination Sum IVComing soonOrder matters here — swap the loops (amount outer) to count permutations.
- Perfect SquaresComing soonUnbounded knapsack where the 'coins' are 1, 4, 9, 16, … — minimise the count.