231. Ways to Make an Amount

Challenge1000 ms256 MBSolved by 0%

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.

Input3 11 1 2 5

Output11

Noteis a small case with three coin values

Input1 0 1

Output1

Noteis an amount of zero, made in exactly one way: use nothing

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution