Dynamic ProgrammingUnbounded Knapsack
With unlimited coins of the given denominations, count the number of different combinations that add up to the amount. Two combinations are the same if they use the same number of each coin (order does not matter). If the amount cannot be made, the answer is 0.
Input
Line 1: n and the amount. Line 2: the n distinct coin values.
Output
Print the number of combinations.
Constraints
1 <= n <= 8 1 <= coin <= 20, all distinct 0 <= amount <= 300 The answer fits in a signed 64-bit integer.
Example 1
Input
3 5 1 2 5
Output
4
Four ways: 5, 2+2+1, 2+1+1+1 and 1x5.
Example 2
Input
1 3 2
Output
0
No combination of 2s makes 3.