Counting Ways, Not Coins

The Idea

Counting ways is a different recurrence from finding the fewest coins. Each coin is introduced once, and every amount asks how many combinations already known can absorb it. Because a coin is never revisited after its pass, 1+2 and 2+1 are the same answer. Swap the loops and you count orderings instead.

Real-World Example

A vending machine audit that has to report how many distinct coin mixes a customer could have paid with. The machine does not care which coin went in first, so the tally counts mixes, not sequences — and the loop order is the difference between a right and a wrong report.

The Code

coins = [1, 2, 5]
target = 5

ways = [0] * (target + 1)
ways[0] = 1                      # one way to pay nothing: take nothing
for coin in coins:               # coins outside: every mix is counted once
    for a in range(coin, target + 1):
        ways[a] += ways[a - coin]

print(ways)           # [1, 1, 2, 2, 3, 4]
print(ways[target])   # 4

ways = [0] * 6
ways[0] = 1
for a in range(1, 6):            # loops swapped on purpose
  for coin in [1, 2, 5]:
      if coin <= a:
          ways[a] += ways[a - coin]
print(ways[5])