Problem Statement
Given an array arr[] of size N, generate the sum of every possible subset.
Return all subset sums.
Brute Force Intuition
Every element has only two choices:
Include it
Exclude it
For N elements:
2 × 2 × 2 × ... N times
which gives:
2^N subsets
We recursively explore both choices for every element and calculate the sum formed.
Pattern Recognition
Whenever you see:
- Generate all subsets
- Pick / Not Pick
- Every possible combination
Think:
Recursion + Backtracking
Recursive Decision Tree
Example:
arr = [2,3]
0
/ \
+2 skip
/ \ / \
+3 skip +3 skip
5 2 3 0
Subset sums:
5 2 3 0
Optimal Java Solution
import java.util.*;
class Solution {
ArrayList<Integer> subsetSums(int[] arr) {
ArrayList<Integer> ans = new ArrayList<>();
solve(0, 0, arr, ans);
Collections.sort(ans);
return ans;
}
private void solve(int index,
int sum,
int[] arr,
ArrayList<Integer> ans) {
if (index == arr.length) {
ans.add(sum);
return;
}
// Pick
solve(index + 1,
sum + arr[index],
arr,
ans);
// Not Pick
solve(index + 1,
sum,
arr,
ans);
}
}
Dry Run
Input
arr = [1,2]
Recursion
Pick 1
Pick 2 -> 3
Skip 2 -> 1
Skip 1
Pick 2 -> 2
Skip 2 -> 0
Output
[0,1,2,3]
Why Recursion Works?
For every element we have exactly two choices:
Take it
Don't take it
Exploring both choices guarantees that every subset is generated exactly once.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(2^N) |
| Space Complexity | O(N) |
Reason:
2^N subsets exist
and recursion depth is:
N
Interview One-Liner
For each element, recursively explore both possibilities—pick and not pick. When we reach the end of the array, the accumulated sum represents one subset sum.
Pattern Learned
Generate All Subsets
+
Pick / Not Pick
=> Backtracking
=> Recursion
Similar Problems
- Subsets
- Subset Sum
- Combination Sum
- Subsequences of String
- Palindrome Partitioning