Count Subsequences Summing to K
Given a list of N non-negative integers A = [a_1, a_2, ..., a_N] and a target integer K, find the number of distinct subsequences of A whose elements sum up to exactly K. A subsequence is formed by deleting zero or more elements from the original list, maintaining the relative order of the remaining elements. Two subsequences are considered distinct if they are formed by choosing elements from different indices, even if the chosen elements have the same value.
Input
The first line contains two integers N and K, separated by a space. The second line contains N space-separated non-negative integers a_1, a_2, ..., a_N.
Output
Print a single integer, the count of subsequences summing to K.
Constraints
1 <= N <= 1000 0 <= K <= 1000 0 <= a_i <= 1000
Example 1
4 5 1 2 3 4
2
Subsequences summing to 5 are {1, 4}, {2, 3}, {1, 2, 2} if repeated, but here we count distinct index combinations so {1,4} and {2,3} are the only ones. Wait, the problem statement said distinct subsequences. For {1,2,3,4} and K=5, {1,4} and {2,3} are the subsequences. The count is 2.
Example 2
3 0 0 0 0
8
The empty subsequence sums to 0. Any single '0' sums to 0. Any pair of '0's sums to 0. All three '0's sum to 0. The count is 8.
Hints
Similar problems
- Count Paths on a LineEasy
- Maximum Sum Non-Adjacent PairsMedium
- Maximum Sum Increasing SubsequenceMedium
- Longest Increasing Subsequence on a PermutationHard
- Lexicographically Smallest PathMedium
- Longest Zigzag SubsequenceMedium
More topics: Hash Map and Hashing problems, Dynamic Programming problems, Recursion problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
4 5 1 2 3 4
3 0 0 0 0