You are given an integer amount and an array of positive, distinct integers coins, where each coin value can be used unlimited times.
Return the number of distinct combinations of coins that sum to exactly amount.
Notes:
2+1
and
1+2
are the same combination.
amount = 0
, there is exactly
one
way: choose no coins.
amount
, integer array
coins
ways
amount = 5, coins = [1,2,5]
→
4
5
,
2+2+1
,
2+1+1+1
,
1+1+1+1+1
amount = 3, coins = [2]
→
0
amount = 0, coins = [1,2]
→
1
0 ≤ amount ≤ 10^4
1 ≤ len(coins) ≤ 300