Exact Change With Unlimited Coins
Problem
A vending machine holds an unlimited supply of coins in each denomination listed in coins. Return True if it can pay back exactly amount, otherwise False.
Examples
Input: coins = [4, 7], amount = 15
Output: True
Why: 4 + 4 + 7 = 15Input: coins = [4, 6], amount = 9
Output: False
Why: every mix of 4s and 6s is evenInput: coins = [5], amount = 0
Output: True
Why: edge case, paying zero needs no coinsHints
0 / 3
Always taking the largest coin fails: with coins 4 and 7, taking 7 first for 16 leaves 9, which no mix of 4s and 7s can pay, even though 4 + 4 + 4 + 4 works. Think in terms of which amounts are payable at all.
An amount a is payable if, for some coin, the amount a minus that coin is payable. Amount 0 is payable with no coins.
Keep a list of booleans indexed by amount, with index 0 set to True. For each coin, walk the amounts upward from the coin's value and mark a payable when a minus the coin is. Walking upward lets the same coin be used again.
Solution
This is the unbounded knapsack with a yes-or-no answer, the feasibility half of coin change. ok[a] says whether amount a can be paid, and a coin makes a payable when a - coin already was. The loop over amounts runs upward, so by the time it reaches a, the entry for a - coin may already include this same coin, which is exactly what an unlimited supply allows. Running it downward would turn this into the use-each-coin-once problem instead. Time is O(len(coins) · amount) and space is O(amount).
def can_pay(coins, amount):
ok = [False] * (amount + 1)
ok[0] = True # zero needs no coins
for coin in coins:
for a in range(coin, amount + 1): # upward: a coin may be reused
if ok[a - coin]:
ok[a] = True
return ok[amount]
print(can_pay([4, 7], 15)) # -> True
print(can_pay([4, 6], 9)) # -> False
print(can_pay([5], 0)) # -> TrueStuck on the idea rather than the code? Coin Change covers it.