Subset Sums
Subset Sums: return the sums of all subsets of the array (all 2ⁿ of them).
- 1 <= n <= 15
- 0 <= nums[i] <= 10⁴
- Output has 2ⁿ entries, which is what caps n
Intuition
The subset sums problem asks for the sum of every subset of an array — all 2ⁿ of them, in any order. Since the output itself has 2ⁿ entries, there is no clever way to be faster than exponential. The task is simply to enumerate correctly and without duplication.
The cleanest framing is a sequence of binary choices. Take the elements one at a time; for each, you either include it in the current subset or leave it out. Two branches per element, n elements deep, and the leaves of that decision tree are exactly the 2ⁿ subsets.
Better still, you never need to build the subsets themselves. Carry a running sum down the recursion instead: the include branch passes sum + a[i], the exclude branch passes sum unchanged. When the index reaches the end of the array, the running sum is one subset's total, ready to record.
That keeps the state to a single integer per frame:
- No lists to copy, no backtracking to undo — the two branches simply receive different numbers.
The same doubling can be done iteratively. Start with [0], and for each element append every existing sum plus that element. The list doubles per element and ends with the same 2ⁿ values, which is often the easier version to reason about.
The purest take-or-skip recursion: at every index there are exactly two branches, and the leaves are the 2^n outcomes. Whenever each element independently is or isn't included, this binary tree is the search space — no used array and no loop, just two calls. Subsets and subset-sum-equals-target are the same tree with different bookkeeping.
Approach
Before reading on: price up what the direct approach costs here, then ask what you may assume the recursive call already handles correctly. Aim for O(2ⁿ) time and O(n) space.
Model each element as an in-or-out choice
At index i with running sum s, make two recursive calls: one with (i + 1, s + a[i]) for including the element, one with (i + 1, s) for excluding it. Every distinct combination of choices produces one subset, so this enumerates all 2ⁿ without repeats.
Record at the base case
When i reaches the length of the array, every element has been decided and s holds that subset's total. Append it to the results and return. This is the only place a value is written, and it fires exactly 2ⁿ times.
Carry the sum instead of the subset
Passing an integer down means there is nothing to copy and nothing to undo on the way back up. No backtracking step is needed at all — a notable simplification compared to problems that must reconstruct the actual subsets.
Consider the iterative doubling version
Begin with sums = [0]. For each element x, replace the list with sums + [s + x for s in sums]. The list doubles per element and finishes with the same 2ⁿ totals. Same complexity, no recursion depth to worry about.
Cost is set by the output size
There are 2ⁿ subsets and each is produced with O(1) work along a path of depth n, giving O(2ⁿ) time overall. Space is O(2ⁿ) for the results plus O(n) for the recursion stack. No algorithm can do better, because listing 2ⁿ values takes 2ⁿ steps.
Solution & live demo
Common pitfalls
Recursing from a loop as if it were a combination problem
for j in range(i, len(nums)):
go(j + 1, s + nums[j])go(i + 1, s + nums[i]) # take go(i + 1, s) # skip
The loop form can be made to work, but it obscures the structure and makes the base case awkward. Take-or-skip states the actual decision — each element is in or out — and each element is visited exactly once per path.
Appending the sum before reaching the end
def go(i, s):
res.append(s)
if i == len(nums): returndef go(i, s):
if i == len(nums):
res.append(s)
returnRecording at every node collects partial sums from halfway down the tree, producing far more than 2^n entries. Only leaves — where every element has been decided — represent complete subsets.
Forgetting to sort the result
return res
return sorted(res)
GFG expects the sums in non-decreasing order, but the recursion emits them in take-first order. The values are right; the sequence isn't.
Edge cases
One subset — the empty one, sum 0.
Sums repeat legitimately; the answer keeps duplicates.