Check if there exists a subsequence with sum K

Real-Life Analogy

Imagine deciding which coins to use to reach an exact amount of money. Each coin represents a choice: include it in the total or leave it out. By recursively considering each coin and updating the target amount, explore every possible combination of coins. The goal is to determine if any combination of coins can exactly meet the target amount. This method effectively tests all possible ways to reach the target by including or excluding each coin, similar to the problem of finding a subsequence with a specific sum.

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.

Dry Run

Approach

Start with the first item and explore two options: including the item in the current expenditure or excluding it.
Recursively repeat the process for the next item with the updated target amount, adjusting the sum accordingly.
Base cases include: achieving the target amount (success), running out of items (failure if target not met), or if the target becomes negative (failure).
Continue this process until all combinations are explored, and determine if any of them meet the exact target amount.

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    // This method recursively checks for the subsequence with the given sum
    bool func(int ind, int sum, std::vector<int> &nums) {
        // Base case: if all elements are processed, check if sum is 0
        if (ind == nums.size()) {
            return sum == 0;
        }
        // Recursive call: include the current element in the subsequence
        // or exclude the current element from the subsequence
        return func(ind + 1, sum - nums[ind], nums) | func(ind + 1, sum, nums);
    }

public:
    // This method initiates the recursive process
    bool checkSubsequenceSum(std::vector<int>& nums, int target) {
        return func(0, target, nums); // Start the recursive process
    }
};

// Main function to test the solution
int main() {
    Solution sol;
    std::vector<int> nums = {1, 2, 3, 4};
    int target = 5;
    std::cout << sol.checkSubsequenceSum(nums, target); // Expected output: true
    return 0;
}
class Solution {
    // This method recursively checks for the subsequence with the given sum
    public boolean solve(int i, int n, int[] arr, int k) {
        // Base case: if the sum k is 0, a subsequence is found
        if (k == 0) {
            return true;
        }
        // Base case: if k is negative, no valid subsequence can be found
        if (k < 0) {
            return false;
        }
        // Base case: if all elements are processed, check if k is 0
        if (i == n) {
            return k == 0;
        }
        // Recursive call: include the current element in the subsequence
        // or exclude the current element from the subsequence
        return solve(i + 1, n, arr, k - arr[i]) || solve(i + 1, n, arr, k);
    }

    // This method initiates the recursive process
    public boolean checkSubsequenceSum(int[] nums, int target) {
        int n = nums.length; // Get the length of the input array
        return solve(0, n, nums, target); // Start the recursive process
    }

    // Main method to test the solution
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {1, 2, 3, 4};
        int target = 5;
        System.out.println(sol.checkSubsequenceSum(nums, target)); // Expected output: true
    }
}
class Solution:
    # This method recursively checks for the subsequence with the given sum
    def solve(self, i, n, arr, k):
        # Base case: if the sum k is 0, a subsequence is found
        if k == 0:
            return True
        # Base case: if k is negative, no valid subsequence can be found
        if k < 0:
            return False
        # Base case: if all elements are processed, check if k is 0
        if i == n:
            return k == 0
        
        # Recursive call: include the current element in the subsequence
        # or exclude the current element from the subsequence
        return self.solve(i + 1, n, arr, k - arr[i]) or self.solve(i + 1, n, arr, k)

    # This method initiates the recursive process
    def checkSubsequenceSum(self, nums, target):
        n = len(nums) # Get the length of the input array
        return self.solve(0, n, nums, target) # Start the recursive process

# Main function to test the solution
if __name__ == "__main__":
    sol = Solution()
    nums = [1, 2, 3, 4]
    target = 5
    print(sol.checkSubsequenceSum(nums, target)) # Expected output: True
class Solution {
    // This method recursively checks for the subsequence with the given sum
    solve(i, n, arr, k) {
        // Base case: if the sum k is 0, a subsequence is found
        if (k === 0) {
            return true;
        }
        // Base case: if k is negative, no valid subsequence can be found
        if (k < 0) {
            return false;
        }
        // Base case: if all elements are processed, check if k is 0
        if (i === n) {
            return k === 0;
        }
        // Recursive call: include the current element in the subsequence
        // or exclude the current element from the subsequence
        return this.solve(i + 1, n, arr, k - arr[i]) || this.solve(i + 1, n, arr, k);
    }

    // This method initiates the recursive process
    checkSubsequenceSum(nums, target) {
        const n = nums.length; // Get the length of the input array
        return this.solve(0, n, nums, target); // Start the recursive process
    }
}

// Main function to test the solution
const sol = new Solution();
const nums = [1, 2, 3, 4];
const target = 5;
console.log(sol.checkSubsequenceSum(nums, target)); // Expected output: true

Complexity Analysis

Time Complexity O(2^n) - Each item has two choices (include or exclude), leading to an exponential number of combinations.

Space Complexity: O(n) - The maximum depth of the recursive call stack is equal to the number of items.

Problem List

Check if there exists a subsequence with sum K

Examples:

Constraints

Hints

Company Tags

Editorial

Real-Life Analogy

Intuition

Dry Run

Approach

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code