Quant Memo
Coding/●●●●●

Count the ways to make change

You have an unlimited supply of coins in given denominations. Instead of the fewest coins, count how many distinct combinations sum to a target amount. Two combinations are the same if they use the same multiset of coins, so 1+2 and 2+1 count once.

coins = [1, 2, 5], amount = 5  ->  4     # {5}, {2,2,1}, {2,1,1,1}, {1,1,1,1,1}
coins = [2],       amount = 3  ->  0
coins = [7],       amount = 0  ->  1     # the empty combination

Return the number of combinations. Target O(amount×#coins)O(\text{amount} \times \#\text{coins}).

Your answer

This one is open-ended. Work it through, then check your reasoning against the full solution.

More Coding questions