Sum of Subsequences

Interview

Time limit2sMemory limit256 MB

Summary

Count how many non-empty subsequences of up to 20 integers sum exactly to a given target S.

Level: Medium4 of 10
Topics: Backtracking, Brute force, Array
Solved: No attempts yet

Problem

Given a sequence of N integers, count how many non-empty subsequences have a sum equal to S.

A subsequence is formed by choosing one or more positions from the sequence. Different choices of positions count separately, even if their values are the same.

Input

The first line contains two integers N and S.

1 <= N <= 20
|S| <= 1,000,000

The second line contains N integers separated by spaces. The absolute value of each integer is at most 100,000.

Output

Print the number of non-empty subsequences whose sum is S.

Examples1

Example 1
Input
```
5 0
-7 -3 -2 5 8
```
Expected output
```
1
```