Count of Subsequences with Given Sum

Moderate

0/80

0 upvote

Problem statement

You are given an array A of N non-negative integers and a target sum S. Your task is to find the total number of subsequences of the array whose elements sum up to S.

A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer N, the size of the array.
The second line contains N space-separated integers, representing the elements of the array A.
The third line contains an integer S, the target sum.

Output Format:

The output should be a single integer representing the total count of subsequences that sum to S.

Note:

The empty subsequence {} is a valid subsequence and has a sum of 0.
The array contains non-negative integers.
Two subsequences are considered different if they are formed from different indices, even if they contain the same values. For example, in A = [1, 1], the subsequences {1} from the first index and {1} from the second index are different.

Sample Input 1:

4
1 2 1 3
3

Sample Output 1:

Explanation for Sample 1:

The subsequences of A = [1, 2, 1, 3] that sum to S = 3 are:
  {1, 2} (using the first '1')
  {2, 1} (using the second '1')
  {3}
  There are a total of 3 such subsequences.

Expected Time Complexity:

The expected time complexity is O(N * S), where N is the size of the array and S is the target sum.

Constraints:

1 <= N <= 50
0 <= A[i] <= 1000
0 <= S <= 1000

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Count of Subsequences with Given Sum

Console