Mastering Subset Sums: Generating All Possible Combinations using Recursion

In technical interviews, you will frequently encounter two types of problems: Decision Problems (where you answer "Yes" or "No") and Generation Problems (where you must find or list all possible outcomes).

The problem from your screenshot is a classic Generation Problem known as Subset Sums I. Instead of checking if a single target sum is possible, your goal here is to calculate the sum of every single possible subset, store them in a list, and return them in sorted order.

This guide will break down this foundational recursion problem step-by-step, building the mental model you need to ace it in an interview.

1. Understanding the Problem

Problem Statement

Given an array of $N$ integers, find the sum of all possible subsets of the array. Return these sums in a single vector/list sorted in increasing order.

Example

Input: arr = [2, 3]
Output: [0, 2, 3, 5]
Explanation: The subsets of [2, 3] are:Sorting [0, 2, 3, 5] gives us our final answer: [0, 2, 3, 5].
- Empty subset [] $\rightarrow$ Sum = 0
- Subset [2] $\rightarrow$ Sum = 2
- Subset [3] $\rightarrow$ Sum = 3
- Subset [2, 3] $\rightarrow$ Sum = 2 + 3 = 5

2. The Intuition: The "Pick vs. Skip" Binary Tree

For any subset generation problem, the core strategy relies on a simple rule: Every element in the array has the right to be included or excluded.

Imagine walking down a path with the array [2, 3]. You encounter the number 2. You have two choices:

Pick 2: Add 2 to your current running sum and move to the next number.
Skip 2: Keep your running sum exactly as it is and move to the next number.

Because every single element offers exactly 2 choices, an array of size $N$ will branch out into exactly $2^N$ unique leaf nodes. Each leaf node represents a completely unique subset.

Why can't we use Dynamic Programming (DP) here?

In the decision version of this problem, we use DP to skip over duplicate states to save time. However, because this problem requires us to collect every single individual subset sum, we cannot skip anything. We absolutely must visit all $2^N$ combinations. Therefore, pure recursion/backtracking is the optimal approach here.

3. Designing the Recursive Structure

To turn this intuition into working code, our recursive function needs a clear state and a definitive stopping point.

The Recursive State

Our function needs to track four things:

ind: The index of the element we are currently evaluating.
sum: The running sum accumulated so far by our choices.
arr: The original input array.
sumSubset: A container (passed by reference) to store the final sum whenever we successfully finish processing a subset.

The Base Case

When do we know a subset is fully formed? When our index ind reaches the end of the array (ind == N).

At this exact moment, our running sum is complete. We push it into our sumSubset vector and return to backtrack and explore other choices.

if (ind == N) {
    sumSubset.push_back(sum);
    return;
}

4. Complete Step-by-Step Dry Run

Let's trace exactly how the code executes for arr = [2, 3] with $N = 2$ . We start our call at func(0, 0) meaning ind = 0, sum = 0.

func(0, 0)
                          /          \
               PICK arr[0]            SKIP arr[0]
               (Add 2 to sum)         (Sum stays 0)
                    /                      \
             func(1, 2)                     func(1, 0)
             /        \                     /        \
       PICK arr[1]   SKIP arr[1]      PICK arr[1]   SKIP arr[1]
      (Add 3)        (Skip 3)        (Add 3)        (Skip 3)
         /              \               /              \
     func(2, 5)     func(2, 2)      func(2, 3)     func(2, 0)
     [Base Case]    [Base Case]     [Base Case]    [Base Case]
    Pushes: 5       Pushes: 2       Pushes: 3       Pushes: 0

func(0,0) calls Pick branch: ind becomes 1, sum becomes 0 + 2 = 2.
func(1,2) calls Pick branch: ind becomes 2, sum becomes 2 + 3 = 5.
func(2,5) hits Base Case (ind == 2). 5 is pushed to our vector. Returns back to func(1,2).
func(1,2) now calls Skip branch: ind becomes 2, sum remains 2.
func(2,2) hits Base Case. 2 is pushed to our vector. Returns.
The execution backtracks all the way to the root func(0,0) and processes the right side (Skip 2), pushing 3 and 0 respectively.

Our final unsorted vector is [5, 2, 3, 0]. Sorting it gives us [0, 2, 3, 5].

5. Clean, Well-Commented C++ Implementation

Here is the clean, object-oriented implementation based on your screenshot structure:

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

using namespace std;

class Solution {
public:
    // Helper recursive function to generate all subset sums
    void calculateSums(int ind, int sum, const vector<int>& arr, int N, vector<int>& sumSubset) {
        // Base Case: If we have considered all elements
        if (ind == N) {
            sumSubset.push_back(sum);
            return;
        }

        // Choice 1: Pick the current element and add its value to the running sum
        calculateSums(ind + 1, sum + arr[ind], arr, N, sumSubset);

        // Choice 2: Do-not pick (skip) the current element; sum remains unchanged
        calculateSums(ind + 1, sum, arr, N, sumSubset);
    }

public:
    vector<int> subsetSums(vector<int> arr, int N) {
        vector<int> sumSubset;
        
        // Start recursion from index 0 with an initial sum of 0
        calculateSums(0, 0, arr, N, sumSubset);
        
        // Sort the generated sums in increasing order as required
        sort(sumSubset.begin(), sumSubset.end());
        
        return sumSubset;
    }
};

int main() {
    Solution solver;
    vector<int> arr = {2, 3};
    int N = arr.size();
    
    vector<int> result = solver.subsetSums(arr, N);
    
    cout << "All subset sums in sorted order: ";
    for (int val : result) {
        cout << val << " ";
    }
    cout << endl;
    
    return 0;
}

Complexity Analysis

Time Complexity: $O(2^N) + O(2^N \log(2^N))$
- The recursion tree branches into $2^N$ leaves, taking $O(2^N)$ time to generate all sums.
- Sorting a vector of size $2^N$ takes $O(2^N \log(2^N))$ time.
- Therefore, the sorting step dominates the final overall time complexity: $O(2^N \log(2^N))$ .
Space Complexity: $O(2^N) + O(N)$
- We use $O(2^N)$ space to store the subset sums in our output vector.
- We use $O(N)$ space on the implicit recursive call stack due to the maximum depth of the tree.

7. Common Pitfalls to Avoid in Interviews

Forgetting to Pass by Reference: In the helper function, always pass your results container (vector<int>& sumSubset) by reference (using &). If you pass it by value, C++ will duplicate the entire vector during every single recursive call, causing a massive performance slowdown and risking a Memory Limit Exceeded (MLE) error.
Sorting Inside the Recursion: Never call sort() inside your recursive function. Sorting should only happen once at the very end after all $2^N$ sums have been fully generated.
Handling Negative Numbers: This recursive structure inherently works perfectly fine with negative numbers. However, remember that if an array contains negative values, the subset sums will not naturally generate in an increasing order, making the final sorting step absolutely mandatory.

Subset Sums I: Generating All Subset Sums Using Recursion in C++