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.
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
python
▶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
Edge cases
Empty array
One subset — the empty one, sum 0.
Duplicate elements
Sums repeat legitimately; the answer keeps duplicates.
06
Complexity
Time
O(2ⁿ)
Space
O(n)
One leaf per subset; recursion depth n.