GeeksforGeeks Medium

Subset Sums

Return the sums of all subsets of the array (all 2ⁿ of them).

recursionsubsets

02

Intuition

Each element makes one binary choice: in or out. Recurse on both branches carrying the running sum; the leaves of that decision tree are exactly the 2ⁿ subset sums.

How to spot this pattern

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.

03

Approach

1

The decision tree

At index i with running sum s, branch to (i+1, s + a[i]) and (i+1, s). Depth n, 2ⁿ leaves.

2

Collect at the base

When i == n the running sum is one subset's total — append it.

3

Iterative alternative

Start with [0]; for each element, extend the list with every existing sum + element. Same doubling, no recursion.

04

Solution & live demo

▶1def subset_sums(nums):
▶2    res = []
▶3    def go(i, s):
▶4        if i == len(nums):
▶5            res.append(s); return
▶6        go(i + 1, s + nums[i])   # take
▶7        go(i + 1, s)             # skip
▶8    go(0, 0)
▶9    return sorted(res)

05

Common pitfalls

Recursing from a loop as if it were a combination problem

✗ Wrong

for j in range(i, len(nums)):
    go(j + 1, s + nums[j])

✓ Right

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

✗ Wrong

def go(i, s):
    res.append(s)
    if i == len(nums): return

✓ Right

def go(i, s):
    if i == len(nums):
        res.append(s)
        return

Recording 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

✗ Wrong

return res

✓ Right

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.

06

Edge cases

Empty array

One subset — the empty one, sum 0.

Duplicate elements

Sums repeat legitimately; the answer keeps duplicates.

07

Complexity

Time

O(2ⁿ)

Space

O(n)

One leaf per subset; recursion depth n.