Given an array of positive integers and a target sum K, generate and print all subsequences of the array whose sum equals K. A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.<\/p>\n\n\n\n
Note: <\/strong>A subsequence is a subset that can be derived from an array by removing zero or more elements, without changing the order of the remaining elements.<\/p>\n\n\n\n Examples:<\/strong> <\/p>\n\n\n\n Input:<\/strong> arr[] = [1, 2, 3], k = 3 Input:<\/strong> arr[] = [1, 2, 3], k = 7 Input:<\/strong> arr[] = [17, 18, 6, 11, 2, 4], k = 6 Imagine you’re packing a bag for a trip, and you want the total weight to be exactly K pounds. For each item in your suitcase (the array), you have two choices: pack it (include it in the sum) or leave it (skip it). You try one choice, see if it leads to the right weight, and if not, you backtrack (unpack the item) and try the other choice. This “try and undo” method is backtracking, it’s like exploring a tree of decisions, where each path is a possible subsequence. We stop when the sum hits K exactly or when we’ve tried all options.<\/p>\n\n\n\n This explores all possible subsequences efficiently, pruning paths that exceed K to save time.<\/p>\n\n\n\n\n
Output:<\/strong> [ [1, 2], [3] ]
Explanation: <\/strong>All the subsequences of the given array are:
[ [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3], [] ]
Out of which only two subsequences have sum of their elements equal to 3.<\/p>\n\n\n\n
Output: <\/strong>[]
Explanation: <\/strong>Sum of all the elements of the array is 6, which is smaller than the required sum, thus they are no subsequences with sum of its elements equal to 7.<\/p>\n\n\n\n
Output:<\/strong> [ [2, 4], [6] ] <\/p>\n<\/blockquote>\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
\n
Code<\/h3>\n\n\n\n