Subsequence Sum Count 2
Time limit1sMemory limit256 MB
Count the number of non-empty subsequences of up to 40 integers whose sum equals a given target S using a meet-in-the-middle approach.
- Level
Medium6 of 10
- Topics
- Brute force, Binary search, Sorting, Array
- Solved
- No attempts yet
Problem
Given a sequence of N integers, count how many non-empty subsequences have sum S.
Two selections are different if they choose different positions, even when the selected values are the same.
Input
The first line contains the number of integers N and the target sum S. (1 ≤ N ≤ 40, |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 subsequences whose sum is S.