Given an amount and a list of coin denominations (positive, reusable), return the
fewest coins that sum to exactly amount, or -1 if it's impossible.
minChange(amount, coins)
Input format: amount | coins.
amount=11, coins=[1, 2, 5] // → 3 (5+5+1)
amount=3, coins=[2] // → -1
amount=0, coins=[1] // → 0
A close cousin of pure reachability, but instead of "can this amount be made?" it asks for the fewest coins. To make amount, use some coin last; after using coin c, make amount - c with as few coins as possible, plus 1 for the coin just used. So the minimum for amount is 1 plus the smallest of minChange(amount - c) over every coin that doesn't overshoot.
amount == 0 needs zero coins. A negative amount means this choice overshot — treat it as impossible (a large placeholder value that never wins a minimum comparison).
Grabbing the biggest coin that fits can fail — coins 1, 3, 4 with target 6: greedily taking 4 then two 1's gives three coins, but 3+3 gives two. You need to consider all options and let the recursion find the true minimum.
Written naively, the recursion revisits the same remaining amounts repeatedly — different coin sequences land on the same leftover, and each gets re-derived from scratch. That redundancy grows exponentially with the amount and number of coin types.
The only thing that matters going forward is the current remaining amount — not the sequence of coins used to get there. Cache from remaining amount to minimum coin count. Check before recursing; if cached, use it. Otherwise try every coin, recurse, take the minimum of 1 + result, cache it. If nothing leads to a valid answer, report -1.
Only amount + 1 distinct remaining amounts exist, each solved once by trying every coin — roughly O(amount × coins) instead of exponential.
def min_change(amount, coins):
INF = float("inf")
memo = {}
def best(a):
if a == 0:
return 0
if a < 0:
return INF
if a in memo:
return memo[a]
m = INF
for c in coins:
sub = best(a - c)
if sub + 1 < m:
m = sub + 1
memo[a] = m
return m
r = best(amount)
return r if r < INF else -1
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.