Author at SyntaxFlow
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.
Given an array of integers, find the sum of all possible subsets of the array. Return these sums in a single vector/list sorted in increasing order.
arr = [2, 3][0, 2, 3, 5][2, 3] are:Sorting [0, 2, 3, 5] gives us our final answer: [0, 2, 3, 5].[] Sum = 0[2] Sum = 2[3] Sum = 3[2, 3] Sum = 2 + 3 = 5For 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:
2: Add 2 to your current running sum and move to the next number.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 will branch out into exactly unique leaf nodes. Each leaf node represents a completely unique subset.
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 combinations. Therefore, pure recursion/backtracking is the optimal approach here.
To turn this intuition into working code, our recursive function needs a clear state and a definitive stopping point.
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.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;
}
Let's trace exactly how the code executes for arr = [2, 3] with . 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: 0func(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.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].
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;
}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.sort() inside your recursive function. Sorting should only happen once at the very end after all sums have been fully generated.