You have unlimited coins of each distinct denomination in coins. Return the number of different combinations of coins that sum to exactly amount. Order doesn't matter: 2 + 1 + 1 and 1 + 2 + 1 are the same combination.
Implement change(amount: int, coins: list[int]) -> int.
change(4, [1, 2]) # 3 1+1+1+1, 1+1+2, 2+2
change(3, [2]) # 0
change(0, [7]) # 1 the empty combination
change(10, [3, 4, 7]) # 2 3+3+4, 3+7
Constraints: 0 <= amount <= 5000, 1 <= len(coins) <= 300, coin values distinct and in [1, 5000].
The count can be large, though it always fits in a 64-bit integer. Listing every combination is far too slow; aim for O(amount × len(coins)).
Show hint
build the counts up one denomination at a time, so that each combination is only ever formed in one order. Counting ways per amount without that discipline counts 1 + 2 and 2 + 1 separately.