Given an amount and coin denominations (positive, reusable), return the number of
distinct combinations of coins that sum to amount. Order doesn't matter:
1+2 and 2+1 are the same combination.
countingChange(amount, coins)
Input format: amount | coins.
amount=4, coins=[1, 2, 3] // → 4 (1+1+1+1, 1+1+2, 2+2, 1+3)
amount=0, coins=[1] // → 1 (use no coins)
amount=5, coins=[2] // → 0
This sounds like min-change's cousin, but it wants distinct combinations, where order doesn't matter — a 1 then a 2 is the same combination as a 2 then a 1, counted once. Recursing the min-change way (try every coin, recurse on the remainder) overcounts, since the same combination gets reached via different coin orders.
Force a canonical order: process coins left to right as a fixed list. At each step ask: using only coins from index i onward, how many ways to make this remaining amount? Two choices: use another copy of coin i (stay at i, reduce the amount), or stop considering coin i (advance to i+1, amount unchanged). Sum both branches. Since you never go back to an earlier index, each combination is built in exactly one order — counted once.
Remaining amount exactly 0 is one valid way. Amount negative, or coins exhausted while amount is still positive, contributes zero.
Even with the ordering fix, a direct implementation revisits the same (remaining amount, coin index) pair through different decision sequences. The answer depends only on that pair — not on the specific path of prior decisions.
Cache keyed by (remaining amount, coin index). Check before recursing; otherwise sum the "reuse this coin" and "move to the next coin" branches, cache, return.
At most (amount + 1) × (coins) distinct pairs exist — roughly O(amount × coins) instead of the much larger redundant call count a naive, unordered approach generates. When a problem wants combinations rather than sequences, impose an artificial order on the choices so each answer is constructed once, then memoize on whatever state fully determines what happens next.
def counting_change(amount, coins):
memo = {}
def ways(remaining, i):
if remaining == 0:
return 1
if remaining < 0 or i >= len(coins):
return 0
key = (remaining, i)
if key in memo:
return memo[key]
v = ways(remaining - coins[i], i) + ways(remaining, i + 1)
memo[key] = v
return v
return ways(amount, 0)
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.