How can I make a program that counts all the subsets that sums a certain number of an array of integers in C++?

The problem is described like this:

Given a set s of integers, your task is to determine how many different non-empty subsets sum up to a target value.

Input

The input consists of several test cases. The first line of each test case is a line containing two integers N and T, the number of items of the original set of integers and the target value. After that comes one line with the N integers si that belong to the original set s.

• 1 ≤ N ≤ 40

• −109 ≤ T, si ≤ 109

Output

For each test case print on a single line an integer indicating the number of different non-empty subsets that sum up to the target value T.

Explication:

On the first test case the target is 0 and the following are the valid subsets: (2, 4, -1, -5), (2, 6, -5, -3), (4, -1, -3), (6, -5, -1).

On the second test case the target is again 0, the only valid subset is: (-3, -2, 5)

Sample Input

6 0

-1 2 -3 4 -5 6

5 0

-7 -3 -2 5 8

Sample Output

4

1