Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Subsets I in Java: Find Every Subset Sum

Understand take-or-skip recursion by producing every subset sum, with repeated sums, commented Java, a recursion tree and a dry run.

EasyRecursion and backtrackingPattern: recursion, backtracking

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

  1. 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.

  2. Example 2 Case 2

    Input
    [1,1]
    Output
    [2,1,1,0]

    The two sums of 1 belong to different index selections.

  3. Example 3 Case 3

    Input
    [0]
    Output
    [0,0]

    Taking zero and skipping it are still two distinct subsets.

Solve on GeeksforGeeks ↗

Hints Optional

Hints become more specific one step at a time.
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

  1. Start at index 0 with sum 0.
  2. If all positions have been decided, save the sum and return.
  3. Take the current position: advance the index and add its value.
  4. 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.

Java
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

Numbered illustrated dry run for Subsets I; the text transcript explains the states.
Follow the numbered panels in order. Open full-size 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.

  1. Start with nothing selected

    Java operationcollectSums(nums, 0, 0, result);
    Stateindex = 0; sum = 0; result = []

    Both positions still need a take/skip decision.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

Worked example · read from top to bottom
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.

Practice next

Next lessonPower Set and subsets

Back to Recursion and backtracking →