Coin Change II

mediumTests passed 2026-11-11v1.0.0
TC: O(A * C)|SC: O(A)
2D DPOriginal Statement (leetcode).md

1. Core Invariant / The Trick

To count **combinations** (order-independent, `[1,2]` == `[2,1]`), place the **coin loop on the outside** and `amount` loop on the inside (`dp[a] += dp[a - c]`). Putting `amount` outside counts *permutations* instead.

2. Complexity Bounds & Proof

Processing each coin denomination completely before unlocking the next enforces canonical non-decreasing coin order inside every combination.

3. Minimal Idiomatic Code

def change(amount: int, coins: list[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]

4. Failure Modes & Interview Follow-ups

Pitfalls:- Swapping loop order (`for a in range... for c in coins`) double-counts `[1,2]` and `[2,1]` as distinct ways!
Follow-ups:- Combination Sum IV explicitly wants ordered permutations and swaps the loop order (`amount` outer, `nums` inner).

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Coin Change (O(A * C))Target Sum (O(N * P))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.