Till Change Combinations

medium

Back at the till — but tonight the question isn't fewest coins, it's how many ways. The till stocks unlimited coins of the given denominations, and the cashier idly counts the distinct combinations that sum exactly to amount.

Order doesn't matter: handing over 2+1 and 1+2 is the same combination. Return the number of distinct combinations. An amount of 0 has exactly one combination — the empty handful.

Example 1

in coins = [1, 2, 5], amount = 5

out 4

5 · 2+2+1 · 2+1+1+1 · 1+1+1+1+1.

Example 2

in coins = [2], amount = 3

out 0

Even sums only.

Constraints

· 1 <= len(coins) <= 12
· 1 <= coins[i] <= 1000
· all denominations distinct
· 0 <= amount <= 1000