Ways to Make Change

You have as many coins as you like of each value in coins. Write count_combinations(coins, amount) that returns how many different ways there are to pay exactly amount.

Only which coins you use matters, not their order: 1 + 2 and 2 + 1 are the same way. Paying 0 has exactly one way, which uses no coins.

Examples

count_combinations([1, 2, 3], 4)    # returns 4
count_combinations([2, 5, 10], 20)  # returns 6
count_combinations([3], 7)          # returns 0

The four ways to pay 4 are 1 + 1 + 1 + 1, 1 + 1 + 2, 2 + 2 and 1 + 3.

Constraints

• 1 <= len(coins) <= 20, and the values are all different
• 1 <= coins[i] <= 5000
• 0 <= amount <= 5000