Print all subsequences with Sum = K: Complete Guide with Backtracking

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.

Note: 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.

Examples:  

Input: arr[] = [1, 2, 3], k = 3 
Output: [ [1, 2], [3] ]
Explanation: 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.

Input: arr[] = [1, 2, 3], k = 7
Output: []
Explanation: 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.

Input: arr[] = [17, 18, 6, 11, 2, 4], k = 6  
Output: [ [2, 4], [6] ] 

Solution: Backtracking Approach

Intuition

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.

Detailed Approach

1. Recursive Function: Create a helper function (backtrack) that takes the current subset, the current index in the array, and the current sum.
2. Base Cases:
   • If the current sum equals K, add a copy of the subset to the result (we found a valid subsequence).
   • If the current sum exceeds K, stop this path (no need to add more).
   • If the index reaches the end of the array, stop (no more elements to consider).
3. Include Choice: Add the current element to the subset, update the sum, and recurse to the next index.
4. Backtrack: After exploring the “include” path, remove the element (pop it) to undo the choice.
5. Exclude Choice: Recurse to the next index without adding the current element (skip it).
6. Start Recursion: Call the function with an empty subset, index 0, and sum 0.
7. Collect Results: The result list will hold all valid subsequences.

This explores all possible subsequences efficiently, pruning paths that exceed K to save time.

Code

from typing import List

def backtrack(subset: List[int], index: int, total: int):
    # Base case: If sum equals K, add a copy of the subset to result
    if total == k:
        result.append(subset.copy())
        return
    # Prune: If sum exceeds K, stop this path
    elif total > k:
        return
    # Base case: If index is out of bounds, stop
    if index >= len(nums):
        return
    
    # Choice 1: Include the current element
    subset.append(nums[index])  # Add to subset
    Sum = total + nums[index]   # Update sum
    backtrack(subset, index + 1, Sum)  # Recurse to next index
    
    # Backtrack: Undo the inclusion
    subset.pop()                # Remove last element
    Sum = total                 # Reset sum
    
    # Choice 2: Exclude the current element
    backtrack(subset, index + 1, Sum)  # Recurse without adding

result = []                     # List to store all valid subsequences
nums = [1, 2, 3, 4, 3, 2, 1, 1, 1, 1]  # Example array
k = 3                           # Target sum
backtrack([], 0, 0)             # Start backtracking
print(result)                   # Print the result

Code Explanation

The backtrack function builds subsequences by making choices at each index. It first tries including the current number (append to subset, add to sum, recurse). Then, it undoes that choice (pop from subset) and tries excluding it (just recurse). If the sum hits K exactly, it saves a copy of the subset. If the sum goes over K or we reach the end, it stops that path. This way, we explore all combinations without duplicates, and the copy ensures each valid subset is stored safely before further changes.

Time and Space Complexity

• Time Complexity: O(2^n) – In the worst case, we explore all possible subsequences (2^n), but pruning (when sum > K) can reduce this in practice.
• Space Complexity: O(n) – The recursion stack can go up to depth n, plus space for the current subset.

Simplifying It

Backtracking is your “trial and error” friend for problems with choices. It’s like trying on clothes: pick one (include), see if it fits your style (sum==K), if not, take it off (backtrack) and try without it. You keep going until you’ve tried all outfits (reach the end). It’s powerful because it systematically covers all options without repeating work, and the “undo” step (pop) lets you reuse the same subset list efficiently. Great for subsets, combinations, or puzzles like Sudoku!

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