Count All Subsequences with Sum = K: Complete Guide with Backtracking

Given an array arr of non-negative integers and an integer target, the task is to count all subsets of the array whose sum is equal to the given target.

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

Examples:

Input: arr[] = [5, 2, 3, 10, 6, 8], target = 10
Output: 3
Explanation: The subsets {5, 2, 3}, {2, 8}, and {10} sum up to the target 10.

Input: arr[] = [2, 5, 1, 4, 3], target = 10
Output: 3
Explanation: The subsets {2, 1, 4, 3}, {5, 1, 4}, and {2, 5, 3} sum up to the target 10.

Input: arr[] = [5, 7, 8], target = 3
Output: 0
Explanation: There are no subsets of the array that sum up to the target 3.

Input: arr[] = [35, 2, 8, 22], target = 0
Output: 1
Explanation: The empty subset is the only subset with a sum of 0.

Constraints:
1 ≤ arr.size() ≤ 10³
0 ≤ arr[i] ≤ 10³
0 ≤ target ≤ 10³

Solution: Backtracking Approach

Intuition

Backtracking is like trying on different outfits for an event – you pick an item (include it in your sum), see if it helps reach the target, and if not, you take it off (backtrack) and try without it. For each element in the array, you have two choices: include it in the current sum or skip it. You recurse through the array, updating the sum, and when you reach the end, check if the sum equals K. If yes, count it as 1 valid way. This explores all possible subsequences and counts only those that match the sum.

Detailed Approach

1. Recursive Function: Create a helper function (backtrack) that takes the array, current index, and current total sum.
2. Base Case: If the index reaches or exceeds the array length, check if the total equals K – if yes, return 1 (valid subsequence), else return 0.
3. Include Choice: Add the current element to the total and recurse to the next index (left branch).
4. Exclude Choice: Skip the current element and recurse to the next index (right branch).
5. Combine Results: Return the sum of the counts from both choices (left + right).
6. Start Recursion: Call the function with index 0 and total 0.
7. Return the Count: The result is the total number of valid subsequences.

Note: We go till the end even if sum exceeds K, but in this basic version, we don’t prune – that’s for learning purposes.

Code

class Solution:
    def backtrack(self, nums, index, total, k):
        # Base case: We've considered all elements
        if index >= len(nums):  # We are going till end because this array may contain zeros
            if total == k:
                return 1  # Valid subsequence found
            return 0  # Not valid
            
        # Choice 1: Include the current element
        Sum = total + nums[index]
        left = self.backtrack(nums, index + 1, Sum, k)
        
        # Choice 2: Exclude the current element
        Sum = total
        right = self.backtrack(nums, index + 1, Sum, k)
        
        # Return total count from both choices
        return left + right
        
    def perfectSum(self, arr, target):
        return self.backtrack(arr, 0, 0, target)

Code Explanation

The backtrack function explores all subsequences by making choices at each index. It tries including the current number (add to total, recurse with index+1), then tries excluding it (keep total the same, recurse with index+1). At the end of the array, it checks if the total matches K and returns 1 if yes, 0 otherwise. The counts from both branches are added up and returned, giving the total number of valid subsequences. No extra data structures are used – just recursion to build the count.

Important Note for Students: This pure recursive approach will give a Time Limit Exceeded (TLE) error on large test cases (e.g., array size up to 30 or more, since it explores 2^n paths without optimization). That’s perfectly fine for learning recursion and backtracking concepts! In real interviews or optimized solutions, we’d add memoization (DP) to avoid recomputing the same states, but here we’re focusing on the basics to build your understanding.

Time and Space Complexity

• Time Complexity: O(2^n) – We make 2 choices (include/exclude) for each of n elements, exploring all subsequences.
• Space Complexity: O(n) – The recursion stack can go up to depth n.

Simplifying It

Backtracking is your go-to for “try all possibilities” problems. It’s like a choose-your-own-adventure book: at each chapter (index), pick option A (include) or B (exclude), and see if you reach the happy ending (sum==K). If not, go back and try the other option. Here, we count the happy endings instead of listing them. It’s simple and builds intuition for harder problems like the 0/1 Knapsack or Combination Sum. Remember, this basic version is for learning – real-world optimizations come later! Practice with small arrays to see the recursion tree. Happy coding! 🚀

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