Check if there exists a subsequence with sum = K | Backtracking Solution in Python

Hey students! If you’re exploring recursion and backtracking, this problem is a great follow-up to subsets or subsequences. It’s like the “Subsets with Sum K” but simpler, instead of finding all, we just check if at least one exists.

We’ll use backtracking to explore possibilities, and I’ll explain it in easy terms so you can grasp how it works. Remember, this is for learning recursion, so we’ll focus on the concept even if it’s not the fastest way.

Here’s the [Problem Link] to begin with.

Given an array arr and target sum k, check whether there exists a subsequence such that the sum of all elements in the subsequence equals the given target sum(k).

Example:

Input:  arr = [10,1,2,7,6,1,5], k = 8.
Output:  Yes
Explanation:  Subsequences like [2, 6], [1, 7] sum upto 8

Input:  arr = [2,3,5,7,9], k = 100. 
Output:  No
Explanation:  No subsequence can sum upto 100

Your Task:
You don’t need to read or print anything. Your task is to complete the boolean function checkSubsequenceSum() which takes N, arr and K as input parameter and returns true/false based on the whether any subsequence with sum K could be found.

Expected Time Complexity: O(N * K).
Expected Auxiliary Space: O(N * K).

Constraints:
1 <= arr.length <= 2000.
1 <= arr[i] <= 1000.
1 <= target <= 2000.

Solution: Backtracking Approach

Intuition

Backtracking is all about trying choices and undoing them if they don’t work. Here, for each element in the array, we have two options: include it in our current sum or skip it. We start from the first element, try including it (add to sum, move to next), check if we hit K, and if not, backtrack (remove it from sum) and try skipping. It’s like searching for a path in a maze where each step is “pick” or “not pick,” and we stop as soon as we find a path that sums to K.

Detailed Approach

1. Recursive Function: Use a helper backtrack that takes the current subset (for tracking), index, and current total sum.
2. Base Cases:
   • If total == K, we’ve found a valid subsequence – return True.
   • If index >= N, we’ve checked all elements without hitting K – return False.
3. Include Choice: Add the current element to the subset and sum, recurse to the next index. If this path returns True, we’re done.
4. Backtrack: Remove the element from the subset (pop) to undo.
5. Exclude Choice: Recurse to the next index without adding to sum.
6. Start Recursion: Call with empty subset, index 0, total 0.
7. Return Result: If any path returns True, yes (1); else no (0).

This explores the decision tree until it finds one valid subsequence or exhausts all options.

Code

class Solution:
    def backtrack(self, subset, index, total):
        if total == K:
            # result.append(subset.copy())  # Uncomment if you want to collect the subset
            return True
        if index >= N:
            return False
        
        subset.append(arr[index])
        pick = self.backtrack(subset, index + 1, total + arr[index])
        if pick == True:
            return True
        
        e = subset.pop()
        # No need for Sum -= e; just pass total for not pick
        return self.backtrack(subset, index + 1, total)
    
    def checkSubsequenceSum(self, N, arr, K):
        return self.backtrack([], 0, 0)

Code Explanation

The backtrack function builds a subset while tracking the sum. It first checks if the current sum equals K (success!). If not, and we’re past the array, it’s a failure. We try including the current element (append to subset, add to total, recurse). If that path finds a match (pick == True), return True early. Otherwise, undo (pop) and try excluding (recurse without changing total). The function returns True if any path succeeds, else False. In checkSubsequenceSum, we start the process and return the boolean (can be converted to 1/0 if needed).

Time and Space Complexity

• Time Complexity: O(2^N) – We explore up to 2^N paths in the worst case (each element picked or not).
• Space Complexity: O(N) – Recursion stack depth up to N, plus subset space.

Simplifying It

Backtracking is your “try everything” tool for choice-based problems. It’s like shopping with a budget: for each item, decide “buy” (add to cart/sum) or “skip.” If your cart totals K, success! If not, remove the last item (backtrack) and try without it. We stop early when we find one (no need to check all if we just want existence). It’s intuitive and builds on subset generation, but remember to backtrack to avoid wrong states.

Note: This backtracking approach may cause TLE (Time Limit Exceeded) on large test cases (e.g., N up to 40), which is perfectly fine as we’re focusing on learning recursion. For optimization, we could add pruning (e.g., if total > K and positives only, skip) or use DP for efficiency, but that’s for later lessons!

Practice by drawing the recursion tree, it’ll help visualize the choices. If you have questions, drop them below. Happy coding! 🚀

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.