Problem statement
Return the sum of each subset of the input array. Include the empty subset, whose sum is zero. This problem’s name is easy to confuse with Power Set: here the answer contains numbers, not lists of selected values.
Positions are independent choices. For [1,1], selecting the first position and selecting the second position both produce sum 1. Keep both occurrences. A set of sums would lose an answer.
The original supplied task permits 1–15 elements with values 0–10,000 and accepts any output order. We follow that contract; the GFG practice destination may use a different wrapper. The method also works for signed values and returns [0] for an empty array as a defensive extension.
Constraints & requirements
- CONTRACT
- Original task: 1–15 elements, values 0–10,000. Return sums, not subsets, and do not deduplicate equal sums. The sample code also handles an empty array as [0].
Examples 3 test cases
Example 1 Case 1
- Input
[2,3]- Output
[5,2,3,0]
Take-first recursion visits both, first only, second only, then neither. Sorted display [0,2,3,5] is equally valid.
Example 2 Case 2
- Input
[1,1]- Output
[2,1,1,0]
The two sums of 1 belong to different index selections.
Example 3 Case 3
- Input
[0]- Output
[0,0]
Taking zero and skipping it are still two distinct subsets.
Hints Optional
01Hint 1
At each index, decide take or skip.
02Hint 2
Carry index and running sum; a temporary subset is unnecessary.
03Hint 3
Save the sum only after deciding every index; each call owns its integer sum.
How to think before coding
Define a call by the next undecided index and the sum of positions already taken. At index==length, save that sum once. Otherwise take the value in one child and skip it in the other, advancing the index in BOTH. Integers are passed by value, so the two child sums cannot corrupt each other. There is no target and no need to save a subset list.
Brute force and the improvement
Try all 2^n index-selection masks. For each mask, scan n positions and add the selected values, then save the sum. That takes O(n·2^n) time and O(1) accumulator space beyond the returned 2^n sums (for a bounded machine-word mask). Repeated sums must remain, because different index selections count separately. Carrying a running sum through take/skip recursion removes the repeated full-mask scan and reaches O(2^n) generation work with O(n) stack space, excluding output.
Intuition: one decision per position
Imagine two switches, one for 2 and one for 3. A switch is either on or off. Turning both on gives 5; turning only the first on gives 2; only the second gives 3; both off gives 0.
Recursion makes the same decisions one position at a time. Its state is (index, sum): which position is next, and how much the chosen positions total. We do not need a temporary array of selected values because only their sum is requested.
Algorithm
- Start at index 0 with sum 0.
- If all positions have been decided, save the sum and return.
- Take the current position: advance the index and add its value.
- Skip it: advance the index without changing the sum.
Both branches must run. This is enumeration, not a yes/no problem that can stop after one successful branch.
Java solution
The two calls receive independent integer sums. No temporary subset list is needed because the requested output contains sums, not selected values.
import java.util.*;
class Solution {
public static List<Integer> subsetSums(int[] nums) {
List<Integer> result = new ArrayList<>(); // Keep one sum per index selection, including repeats.
collectSums(nums, 0, 0, result); // No positions decided yet; empty selection has sum zero.
return result; // Any order is accepted; do not sort just to calculate sums.
}
private static void collectSums(int[] nums, int index, int sum, List<Integer> result) {
if (index == nums.length) { // Each index has now received exactly one take/skip decision.
result.add(sum); // Save only the sum; no temporary subset array is needed.
return; // A completed selection has no next element.
}
collectSums(nums, index + 1, sum + nums[index], result); // Take this index.
collectSums(nums, index + 1, sum, result); // Skip it; this call has its own unchanged sum.
}
public static void main(String[] args) {
System.out.println(subsetSums(new int[]{2, 3})); // [5, 2, 3, 0]
}
}The default invocation prints [5, 2, 3, 0]. That is the exact take-first traversal order. Sorting would display [0,2,3,5], but it is not needed to meet this task’s contract.
Recursion tree and dry run

Read the text transcript
Follow the Java, step by step
Example: nums = [2,3]
What to track: Track index and sum in each frame. Integers are passed by value; result is shared. This is the complete take-first traversal.
-
Start with nothing selected
Java operationcollectSums(nums, 0, 0, result);Stateindex = 0; sum = 0; result = []Both positions still need a take/skip decision.
-
Take 2, then take 3
Java operationcollectSums(nums, index + 1, sum + nums[index], result);Statecalls: (index=1, sum=2), then (index=2, sum=5)At index 2 every position has been decided. The leaf saves 5 and returns.
-
Skip 3 in the waiting frame
Java operationcollectSums(nums, index + 1, sum, result);Stateresumed (index=1, sum=2) creates leaf (index=2, sum=2); result = [5,2]The parent still has sum = 2. No subtraction or mutable-path undo is necessary.
-
Skip 2 at the root, then take 3
Java operationcollectSums(nums, index + 1, sum + nums[index], result);Stateroot’s skip child is (index=1, sum=0); its take child is (index=2, sum=3); result = [5,2,3]Returning from the entire take-2 subtree resumes the root’s own sum = 0.
-
Skip both positions
Java operationresult.add(sum);Statelast leaf: index = 2; sum = 0; result = [5,2,3,0]The empty selection is a real subset. Repeated sums would also be kept, since selections are index-based.
Final result: [5,2,3,0], one sum for each index selection, including the empty selection.
sum(0, 0) ├─ take 2: sum(1, 2) │ ├─ take 3: sum(2, 5) → save 5 │ └─ skip 3: sum(2, 2) → save 2 └─ skip 2: sum(1, 0) ├─ take 3: sum(2, 3) → save 3 └─ skip 3: sum(2, 0) → save 0
When sum(2,5) returns, the waiting parent still owns sum 2. Java passes the integer value to each child; the child cannot change the parent’s local integer. That is why there is no sum -= nums[index] undo statement here. A shared list would need undo, but an integer passed to a child does not.
| State | What happens | Reason |
|---|---|---|
| index 0, sum 0 | Try take 2 | First switch on |
| index 1, sum 2 | Try take 3 | Second switch on |
| index 2, sum 5 | Save 5 | Both positions decided |
| Back at index 1, sum 2 | Try skip 3 | Parent’s sum was never overwritten |
| Back at index 0, sum 0 | Try skip 2 | Explore the other half of the choices |
Why it works
Every subset makes exactly one take/skip decision at every index. The tree contains both decisions at each level, so every index selection reaches one leaf. The running sum equals the selected values’ sum, and the leaf saves exactly that sum. Different selections with equal sums remain different leaves.
Complexity and alternative approaches
There are 2^n leaves and fewer than 2^(n+1) calls. Each call does constant work: O(2^n) time, O(n) auxiliary stack space, and O(2^n) output space. Do not automatically write O(n·2^n): we save one integer, not a copied length-n subset.
Bitmask enumeration is another approach, but scanning n bits per mask costs O(n·2^n). If you deliberately sort the sums afterward, add O(2^n log(2^n)) sorting time. A DP that records only reachable totals answers a different question and loses multiplicities unless it is specifically counting them.
Common mistakes
- Using a set removes repeated sums, including the two zeros for
[0]. - Saving at every internal node adds unfinished decisions more than once.
- Forgetting the skip branch misses the empty subset and many others.
- Printing subsets instead of sums solves Power Set, not Subsets I.