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 .
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.