229. Coin-Change Combination Count

Why this mechanism works

Make coin type the outer loop. After processing a type, ways[x] counts combinations using only types seen so far. Ascending amounts permit multiple copies of the current coin; retaining the existing ways[x] preserves combinations using none. This fixes a canonical type order and avoids counting permutations.

State and boundaries

Before a coin pass, ways uses earlier types. During its ascending pass, ways[x-coin] already allows the current type.

Protocol

1. Sort distinct denominations.
2. Initialize ways[0]=1 and other counts zero.
3. For each coin scan amounts from coin upward.
4. Add ways[amount-coin] into ways[amount].
5. Return the target count.

Visualization

coins [1,2], amount 3
after coin 1: ways [1,1,1,1]
after coin 2: ways [1,1,2,2]
3 = 1+1+1 or 1+2, not separately 2+1

Python implementation

def coin_combinations(coins, amount):
    ways = [0] * (amount + 1)
    ways[0] = 1
    for coin in sorted(set(coins)):
        for total in range(coin, amount + 1):
            ways[total] += ways[total - coin]
    return ways[amount]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 coin_combinations: ways = [0] * (amount + 1)
coins=[1, 2, 5]; amount=5; ways=[0, 0, 0, 0, 0, 0]

L3 coin_combinations: ways[0] = 1
coins=[1, 2, 5]; amount=5; ways=[1, 0, 0, 0, 0, 0]

L4 coin_combinations: for coin in sorted(set(coins)):
coins=[1, 2, 5]; amount=5; ways=[1, 0, 0, 0, 0, 0]; coin=1

L5 coin_combinations: for total in range(coin, amount + 1):
coins=[1, 2, 5]; amount=5; ways=[1, 0, 0, 0, 0, 0]; coin=1; total=1

L6 coin_combinations: ways[total] += ways[total - coin]
coins=[1, 2, 5]; amount=5; ways=[1, 1, 0, 0, 0, 0]; coin=1; total=1

L5 coin_combinations: for total in range(coin, amount + 1):
coins=[1, 2, 5]; amount=5; ways=[1, 1, 0, 0, 0, 0]; coin=1; total=2

L6 coin_combinations: ways[total] += ways[total - coin]
coins=[1, 2, 5]; amount=5; ways=[1, 1, 1, 0, 0, 0]; coin=1; total=2

L5 coin_combinations: for total in range(coin, amount + 1):
coins=[1, 2, 5]; amount=5; ways=[1, 1, 1, 0, 0, 0]; coin=1; total=3

... 12 intermediate state changes omitted ...

L5 coin_combinations: for total in range(coin, amount + 1):
coins=[1, 2, 5]; amount=5; ways=[1, 1, 2, 2, 3, 1]; coin=2; total=5

L6 coin_combinations: ways[total] += ways[total - coin]
coins=[1, 2, 5]; amount=5; ways=[1, 1, 2, 2, 3, 3]; coin=2; total=5

L4 coin_combinations: for coin in sorted(set(coins)):
coins=[1, 2, 5]; amount=5; ways=[1, 1, 2, 2, 3, 3]; coin=5; total=5

L6 coin_combinations: ways[total] += ways[total - coin]
coins=[1, 2, 5]; amount=5; ways=[1, 1, 2, 2, 3, 4]; coin=5; total=5

L2 coin_combinations: ways = [0] * (amount + 1)
coins=[2]; amount=3; ways=[0, 0, 0, 0]

L3 coin_combinations: ways[0] = 1
coins=[2]; amount=3; ways=[1, 0, 0, 0]

L4 coin_combinations: for coin in sorted(set(coins)):
coins=[2]; amount=3; ways=[1, 0, 0, 0]; coin=2

L5 coin_combinations: for total in range(coin, amount + 1):
coins=[2]; amount=3; ways=[1, 0, 0, 0]; coin=2; total=2

L6 coin_combinations: ways[total] += ways[total - coin]
coins=[2]; amount=3; ways=[1, 0, 1, 0]; coin=2; total=2

L5 coin_combinations: for total in range(coin, amount + 1):
coins=[2]; amount=3; ways=[1, 0, 1, 0]; coin=2; total=3

Why the solution is correct

Combinations split into those using zero copies of the current coin and those using at least one. The old state counts the former; removing one current coin maps the latter to the already-updated smaller amount. These disjoint classes cover every combination exactly once.

Time and space

O(C*A+C log C) arithmetic operations and O(A+C) integer storage; exact counts can require multiple machine words.

Common mistakes

Putting amount outside and coins inside counts different orders separately. Descending amount order would restrict each coin type to one use.

Reasoning card

Transfer exercise

Count ordered coin sequences by intentionally reversing the loop hierarchy, and demonstrate the changed answer on amount 3 with coins 1 and 2.