Problem Statement

Given an array nums and an integer k. Return the number of non-empty subsequences of nums such that the sum of all elements in the subsequence is equal to k.

Examples

Example 1:

Input: nums = [4, 9, 2, 5, 1], k = 10
Output: 2

Explanation: The possible subsets with sum k are [4, 5, 1] and [9, 1].

Example 2:

Input: nums = [4, 2, 10, 5, 1, 3], k = 5
Output: 3

Explanation: The possible subsets with sum k are [4, 1], [2, 5, 3] and [5]

Example 3:

Input: nums = [1, 10, 4, 5], k = 16
Output: 1

Explanation: The possible subsets with sum k are [1, 10, 5]

Different Approaches

1️⃣ Recursion

Code:

#include <iostream>
#include <vector>
using namespace std;

int countSubsequences(int ind, int n, vector<int>& nums, int K) {
    // Base case 1: If the sum becomes 0, we found a subsequence with sum K
    if (K == 0) return 1;
    
    // Base case 2: If we've processed all elements or sum becomes negative
    if (ind == n || K < 0) return 0;

    // Recursive case: Try both including and excluding the current element
    // Option 1: Include the current element
    int include = countSubsequences(ind + 1, n, nums, K - nums[ind]);

    // Option 2: Exclude the current element
    int exclude = countSubsequences(ind + 1, n, nums, K);

    // Return the sum of both inclusion and exclusion paths
    return include + exclude;
}

int main() {
    vector<int> nums = {1, 2, 3, 4};
    int K = 5;

    // Count the number of subsequences with sum K
    int result = countSubsequences(0, nums.size(), nums, K);

    cout << "The number of subsequences with sum " << K << " is: " << result << endl;

    return 0;
}