Number of ways to pay an amount with unlimited coins

Dynamic programming Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
coins, amount = [1, 2], 4
combos = [1] + [0] * amount
for c in coins:
    for a in range(c, amount + 1):
        combos[a] += combos[a - c]
orders = [1] + [0] * amount
for t in range(1, amount + 1):  # totals outside
    for step in coins:
        if step <= t:
            orders[t] += orders[t - step]
print(combos[amount], orders[amount])

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 3 5

Right: {1111, 112, 22} as combinations, but five orderings.

Same table and same additions; only the loop order decides whether order matters.

Why not the others?
  • B 5 3. The coin-outside loop is the one that counts combinations.
  • C 3 3. Orderings count 1 + 1 + 2, 1 + 2 + 1 and 2 + 1 + 1 separately.

30-second answer

Let ways[a] count combinations for amount a, with ways[0] = 1. Process one coin value at a time, and for each, sweep amounts upward adding ways[a - c]. Because coins are the outer loop, each combination is built in one fixed coin order and counted once. O(amount × coins) time, O(amount) memory.

Practise saying it · 45 s. No recording, just a timer

Explain counting coin combinations.

Say your answer out loud, then check which of these points you covered:

  • ways[a] += ways[a - c]
  • Coins in the outer loop
  • O(amount × coins)

Deep dive

Loop order is the whole trick: coins outside counts combinations; amounts outside counts orderings.

Sweeping upward allows reusing the same coin; sweeping downward would allow each coin once.

Python ints never overflow, so large counts are fine.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def pay_ways(coins: list[int], amount: int) -> int:
    ways = [1] + [0] * amount  # one way to pay 0: no coins
    for c in coins:  # one coin value at a time: no reorderings
        for a in range(c, amount + 1):
            ways[a] += ways[a - c]
    return ways[amount]

Common mistakes

  • Swapping the loops and counting orderings by mistake.
  • Starting ways[0] at 0, which makes everything 0.

Senior take & follow-ups

Explain the loop order with the 1 + 2 versus 2 + 1 example.

Follow-up questions

Think of your answer first, then open the hint.

  1. What does the other loop order count?

    Show hint

    Ordered sequences, such as the ways to reach a total with steps of given sizes.

  2. How do you limit each coin to one use?

    Show hint

    Sweep the amounts downward for each coin.

What each operation costs: Two Dimensional Arrays

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.