Count Coin Change Combinations
Problem statement
Count the distinct combinations of coins whose values sum to amount. Every denomination in coins is available in unlimited quantity. Two combinations differ only when some denomination is used a different number of times; coin order does not matter.
Return the number of combinations as a 64-bit integer. Amount zero has one combination, choosing no coins. If a positive amount cannot be made, return zero. With no denominations, only amount zero can be made.
Function
countCoinCombinations(coins: int[], amount: int) → longExamples
Example 1
coins = [1,2,5]amount = 5return = 4The four combinations are 5, 2+2+1, 2+1+1+1, and 1+1+1+1+1. Reordering the same coins does not produce a new combination.
Example 2
coins = [2]amount = 3return = 0Any number of value-2 coins has an even sum, so none totals 3.
Example 3
coins = []amount = 0return = 1There is exactly one combination for amount zero: choose no coins. It remains valid when no denominations are available.
Constraints
0 <= coins.length <= 201 <= coins[i] <= 100- The denominations are strictly increasing.
0 <= amount <= 50