Summer Institute '17 Contest 1 P8 - Mo' Money
Max has a number of coins and wants to know how many ways he can use some or all of the coins to reach a target value. Can you write a program to help him out?
The first line of input will contain two space separated positive integers, 𝑛 (𝑛≤15), the number of coins Max has, and 𝑡 (𝑡≤106), the target value he wants to reach. The second line of input will contain 𝑛 space separated positive integers, 𝑎1 through 𝑎𝑛, where 𝑎𝑖 (𝑎𝑖≤5∗105) is the value of the 𝑖th coin.
Output a single integer on a line by itself, representing the number of ways Max can combine his coins to reach his target value.
Sample Input 1
6 20 3 10 4 7 3 6
Sample Output 1
Sample Input 2
10 3500 1000 500 750 250 100 800 1200 900 1300 3000
Sample Output 2