231. Ways to Make an Amount
You have n coin values and unlimited coins of each. Print how many
different combinations make exactly t.
Combinations, not orderings. Making 4 from coins of 1 and 2 gives three
answers: 1+1+1+1, 1+1+2 and 2+2. Counting 1+2 and 2+1
separately would give more, and is a different question.
That distinction decides the shape of the solution. Consider the coins one at a time and decide how the amount is made using only the coins up to that point. Looping over all coins at every step counts orderings instead, and is the commonest way to get this wrong.
Constraints - `1 ≤ n ≤ 20` - `0 ≤ t ≤ 1000` - `1 ≤ coin value ≤ 1000`
Input
The first line contains two integers n and t.
The second line contains n distinct coin values.
Output
Print one integer, the number of combinations that total exactly t.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.