Ways to Pay an Amount
Problem
A vending machine accepts coins of a few distinct positive values, and it has an unlimited supply of each. Given the coin values and an amount, return how many different collections of coins add up to exactly that amount. The order in which coins are inserted does not matter, so 2 + 3 and 3 + 2 are the same collection, and an amount of 0 has exactly one collection: no coins.
Examples
Input: coins = [2, 3, 5], amount = 10
Output: 4
Why: 2+2+2+2+2, 2+2+3+3, 5+5 and 2+3+5Input: coins = [4], amount = 6
Output: 0
Why: no number of fours makes sixInput: coins = [3, 7], amount = 0
Output: 1
Why: edge case, the empty collection pays nothingHints
0 / 3
Counting sequences of coins would count 2 + 3 and 3 + 2 twice. You need a way to build every collection in only one order.
Decide the coins one value at a time: first everything you can make with the first coin only, then allow the second coin, and so on. A collection is then built in coin order and counted once.
Keep a table where ways[a] counts collections for amount a, with ways[0] = 1. For each coin c in turn, go through the amounts from c upwards and add ways[a - c] to ways[a]. The coin loop must be the outer loop.
Solution
Processing the coins in an outer loop means that when coin c is being added, the table already counts every collection that uses only earlier coins. Walking the amounts upward lets the same coin be used again, since ways[a - c] may already include copies of c. Because each collection is built by adding its coins in coin order, it is counted exactly once, and swapping the two loops would count orderings instead. Time is O(k × amount) for k coin values, and space is O(amount).
def count_ways(coins, amount):
ways = [1] + [0] * amount # one way to pay 0: no coins
for c in coins: # each coin value gets exactly one pass
for a in range(c, amount + 1):
ways[a] += ways[a - c] # collections that use at least one more c
return ways[amount]
print(count_ways([2, 3, 5], 10)) # -> 4
print(count_ways([4], 6)) # -> 0
print(count_ways([3, 7], 0)) # -> 1Stuck on the idea rather than the code? Counting Ways, Not Coins covers it.