Check if there Exists a Subsequence with Sum K

Problem Statement

Given an array nums and an integer k. Returns true if there exists subsequences such that the sum of all elements in subsequences is equal to k else false.

Examples

Example 1:

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

Explanation:
The subsequences like [1, 2, 5], [1, 3, 4], [3, 5] sum up to 8.

Example 2:

Input: nums = [4, 3, 9, 2], k = 10
Output: No

Explanation:
No subsequence can sum up to 10.

Example 3:

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

Explanation:
The subsequences like [1, 10, 5] sum up to 16.

Different Approaches

1️⃣ Iteration

Code:

class Solution{
    public:
    bool checkSubsequenceSum(vector<int>& nums, int k) {
         int n = nums.size();
         int totalSubsequences = 1 << n;

         for (int mask = 0; mask < totalSubsequences; mask++) {
            int sum = 0;
            for (int i = 0; i < n; i++) {
                if(mask & (1 << i)){
                    sum = sum + nums[i];
                }
                if(sum == k) {
                    return true;
                }
            }
                
         }
         return false;
    }
};

2️⃣ Recursion:

Intuition:

The problem involves determining whether a subsequence of a given array can sum up to a specified target. By recursively exploring all possible ways to include or exclude each element of the array, the goal is to find out if any combination of these elements can achieve the target sum. The challenge is to exhaustively check all potential subsequences and see if their sum matches the target value.

Approach:

1. Base Cases:
   • If the target K becomes zero, return true, as we've found a valid subsequence whose sum equals K.
   • If the index exceeds the length of the array or K becomes negative, return false.
2. Recursive Case:
   • For each element, we try:
     1. Including the element (subtract it from K and move to the next element).
     2. Excluding the element (move to the next element without subtracting).

If either of these choices leads to a valid subsequence (i.e., returns true), then we return true.

Code:

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

bool isSubsequenceSum(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 true;
    
    // Base case 2: If we've processed all elements or sum becomes negative
    if (ind == n || K < 0) return false;

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

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

    // Return true if either including or excluding gives a valid subsequence
    return include || exclude;
}

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

    // Check if there's a subsequence with sum K
    if (isSubsequenceSum(0, nums.size(), nums, K)) {
        cout << "There exists a subsequence with sum " << K << endl;
    } else {
        cout << "No subsequence with sum " << K << " found" << endl;
    }

    return 0;
}

Explanation of the Code:

1. Base Case 1: if (K == 0) return true;
   • If K becomes zero, it means we found a valid subsequence whose sum equals K, so we return true.
2. Base Case 2: if (ind == n || K < 0) return false;
   • If we've processed all elements or K becomes negative (this means we overshot), return false.
3. Recursive Calls:
   • bool include = isSubsequenceSum(ind + 1, n, nums, K - nums[ind]);: Here, we include the current element and reduce K by the element's value.
   • bool exclude = isSubsequenceSum(ind + 1, n, nums, K);: Here, we exclude the current element and just move to the next one.
4. Return Statement:
   • return include || exclude;: If either the inclusion or exclusion path results in finding a subsequence with sum K, return true.

Example Walkthrough:

For the array nums = {3, 1, 4, 2, 5} and K = 6:

1. Starting with nums[0] = 3:
   • Include: Now K = 6 - 3 = 3.
   • Exclude: Continue with K = 6.
2. With nums[1] = 1:
   • Include: Now K = 3 - 1 = 2.
   • Exclude: Continue with K = 3.
3. With nums[2] = 4:
   • Include: Now K = 2 - 4 = -2. This is invalid, so backtrack.
   • Exclude: Continue with K = 2.
4. With nums[3] = 2:
   • Include: Now K = 2 - 2 = 0. Success! A subsequence {3, 2, 1} sums to 6.

Complexity Analysis:

• Time Complexity: O(2^n) because we explore two choices (include or exclude) for each element in the array.
• Space Complexity: O(n), Due to the recursion stack, where n is the number of elements in the array.