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. <\/p>\n\n\n\n
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.<\/p>\n\n\n\n
Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n Given an array arr <\/strong>and Your Task:<\/strong> Expected Time Complexity:<\/strong> O(N * K). Constraints:<\/strong> 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.<\/p>\n\n\n\n This explores the decision tree until it finds one valid subsequence or exhausts all options.<\/p>\n\n\n\n
\n\n\n\ntarget sum k<\/strong><\/code>, check whether there exists a subsequence such that the sum of all elements in the subsequence equals the given target sum(k).<\/code><\/p>\n\n\n\n
Example:<\/strong><\/p>\n\n\n\nInput: <\/strong> arr = [10,1,2,7,6,1,5], k = 8.\nOutput: <\/strong> Yes\nExplanation: <\/strong> Subsequences like [2, 6], [1, 7] sum upto 8\n\nInput: <\/strong> arr = [2,3,5,7,9], k = 100. \nOutput: <\/strong> No\nExplanation: <\/strong> No subsequence can sum upto 100<\/pre>\n\n\n\n
You don’t need to read or print anything. Your task is to complete the boolean function checkSubsequenceSum()<\/strong> 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.<\/p>\n\n\n\n
Expected Auxiliary Space:<\/strong> O(N * K).<\/p>\n\n\n\n
1 <= arr.length <= 2000.
1 <= arr[i] <= 1000.
1 <= target <= 2000.<\/p>\n\n\n
\n\n\n\nSolution: Backtracking Approach<\/h2>\n\n\n\n
Intuition<\/h3>\n\n\n\n
Detailed Approach<\/h3>\n\n\n\n
\n
backtrack<\/code> that takes the current subset (for tracking), index, and current total sum.<\/li>\n\n\n\n\n
Code<\/h3>\n\n\n\n