L10. Subset Sum I | Recursion | C++ | Java

Master the classic Subset Sum problem from the Striver Striver's SDE/HD Sheet. This chapter covers the exact mechanics of generating all subset sums using recursion, analyzing the exponential time complexity ($O(2^n)$), contrasting naive brute force with optimized choice-based decision trees, and implementing the solution in both C++ and Java.

1. Problem Statement & The Core Objective

Given a list of $N$ integers, your task is to calculate the sums of all possible subsets that can be formed from the list. The final output must be returned sorted in increasing (ascending) order.

• Expected Time Complexity: $O(2^n \log(2^n))$ or $O(2^n \cdot n)$ due to sorting $2^n$ elements.
• Expected Space Complexity: $O(2^n)$ to store all subset sums (note: the problem statement often erroneously specifies $O(N)$ space, but since there are $2^n$ subsets, storing all sums inherently requires $2^n$ space).

2. Concrete Example & Output Generation

Consider an input list of $N = 3$ integers: [3, 1, 2].

If we generate every possible combination of picking or omitting elements:

• Pick none (Null subset): Sum = 0
• Pick [3]: Sum = 3
• Pick [1]: Sum = 1
• Pick [2]: Sum = 2
• Pick [3, 1]: Sum = 4
• Pick [3, 2]: Sum = 5
• Pick [1, 2]: Sum = 3
• Pick [3, 1, 2]: Sum = 6

Sorted Subset Sums Output

Collecting all 8 ($2^3$) subset sums and sorting them in ascending order yields: [0, 1, 2, 3, 3, 4, 5, 6]

3. Why Do We Need Recursion? (Status Quo vs. Better Approach)

The Naive Brute Force Approach (Power Set Algorithm)

• You can generate all subsets using bit manipulation (Power Set).
• The power set algorithm takes $O(2^n \cdot n)$ time.
• However, interviewers will typically push you to optimize away any redundant overhead, leading straight to the elegant Include/Exclude Recursive Pattern.

The Optimal Recursive Mental Model

Instead of generating explicit subset arrays and summing them up later, we can compute the running sum directly on-the-fly. For every index in our array, we face a binary choice:

1. Pick (Include) the element at the current index into our subset.
2. Not Pick (Exclude) the element at the current index.

By making this binary choice for every single index from 0 to N - 1, we traverse all $2^n$ possibilities cleanly.

4. Step-by-Step Recursive Decision Tree Walkthrough

Let's trace our example array [3, 1, 2] ($N = 3$) through the recursive decision tree. At each node, we track (index, current_sum).

5. Pseudocode & Recursive Transition Logic

The core logic boils down to two recursive branches at every step:

Function subsetSumsHelper(index, currentSum, arr, N, answerList):
    // Base Case: If we have processed all elements
    if index == N:
        answerList.add(currentSum)
        return

    // Choice 1: PICK the current element
    subsetSumsHelper(index + 1, currentSum + arr[index], arr, N, answerList)

    // Choice 2: NOT PICK the current element
    subsetSumsHelper(index + 1, currentSum, arr, N, answerList)

6. Complete Implementation in Java

Here is the clean, production-ready Java implementation:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SubsetSum {

    private static void subsetSumsHelper(int index, int sum, ArrayList<Integer> arr, int N, ArrayList<Integer> sumSubset) {
        // Base Case
        if (index == N) {
            sumSubset.add(sum);
            return;
        }

        // Choice 1: Include the element at the current index
        subsetSumsHelper(index + 1, sum + arr.get(index), arr, N, sumSubset);

        // Choice 2: Exclude the element at the current index
        subsetSumsHelper(index + 1, sum, arr, N, sumSubset);
    }

    public static ArrayList<Integer> subsetSums(ArrayList<Integer> arr, int N) {
        ArrayList<Integer> sumSubset = new ArrayList<>();
        subsetSumsHelper(0, 0, arr, N, sumSubset);
        
        // The problem requires subset sums in increasing order
        Collections.sort(sumSubset);
        return sumSubset;
    }

    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<>();
        arr.add(3);
        arr.add(1);
        arr.add(2);
        
        ArrayList<Integer> ans = subsetSums(arr, arr.size());
        System.out.println("Subset Sums: " + ans);
    }
}

7. Complete Implementation in C++

Here is the clean, production-ready C++ implementation:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
private:
    void subsetSumsHelper(int index, int sum, vector<int>& arr, int N, vector<int>& sumSubset) {
        // Base Case
        if (index == N) {
            sumSubset.push_back(sum);
            return;
        }

        // Choice 1: Include the element at the current index
        subsetSumsHelper(index + 1, sum + arr[index], arr, N, sumSubset);

        // Choice 2: Exclude the element at the current index
        subsetSumsHelper(index + 1, sum, arr, N, sumSubset);
    }

public:
    vector<int> subsetSums(vector<int>& arr, int N) {
        vector<int> sumSubset;
        subsetSumsHelper(0, 0, arr, N, sumSubset);
        
        // Sort the sums in increasing order as requested
        sort(sumSubset.begin(), sumSubset.end());
        return sumSubset;
    }
};

int main() {
    Solution sol;
    vector<int> arr = {3, 1, 2};
    vector<int> ans = sol.subsetSums(arr, arr.size());
    
    cout << "Subset Sums: ";
    for (int sum : ans) {
        cout << sum << " ";
    }
    cout << endl;
    
    return 0;
}

8. Complexity Analysis Summary

Summary and Key Takeaways

• Problem Core: Generate all subset sums for an array of size $N$ and return them in ascending order.
• Mental Model: Every element presents a binary choice—Pick or Not Pick—forming a complete binary recursion tree of height $N$.
• Total Subsets: For $N$ elements, exactly $2^n$ subsets (and subset sums) are generated.
• Base Case: Triggered when index == N, indicating decisions have been made for all elements, allowing us to record the accumulated sum.
• Sorting Requirement: Because the problem demands output in increasing order, sorting the resulting $2^n$ collection is mandatory.
• Complexity Reality: Time complexity is driven by the exponential growth of subsets ($O(2^n)$) combined with sorting overhead (O(2^n \log(2^n))}).