You have unlimited coins of each denomination in coins. Return the smallest number of coins whose values add up to exactly amount, or -1 if no combination works. An amount of 0 needs 0 coins.
Implement coin_change(coins: list[int], amount: int) -> int.
coin_change([1, 5, 6, 9], 11) # 2 (5 + 6; greedy 9 + 1 + 1 would use 3)
coin_change([4, 6], 7) # -1
coin_change([3], 0) # 0
Constraints: 1 <= len(coins) <= 12, 1 <= coins[i] <= 2^31 - 1, 0 <= amount <= 10^4.
Greedy (take the largest coin that fits) is wrong for arbitrary denominations, and trying every combination is exponential. Aim for O(amount × len(coins)).
Show hint
the fewest coins for an amount a is one coin plus the fewest coins for whatever is left after that coin. Work out every smaller amount first.