☕ DSA Java Articles

Topics › Recursion and Backtracking › Subsequences Pattern

Subsets I

Medium TUF ID 867 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an array nums of n integers. Return the sum of every subset of nums: one number per subset, so the answer has exactly 2^n entries, including 0 for the empty subset. Equal sums coming from different subsets are all kept. The sums may be returned in any order; the methods below return them in non-decreasing order so the output is deterministic and easy to compare.

This is the problem that the A2Z sheet lists as “Subset Sum-I” (also known as “Subset Sums” on other sheets). It is the simplest member of the subsequence family: no target to hit, no duplicates to remove, just visit every subset once and report its sum. The last section shows how the same recursion produces the subsets themselves, which is what some readers expect from the title.

Constraints: 0 ≤ n ≤ 15, -10^4 ≤ nums[i] ≤ 10^4, so every sum fits comfortably in an int.

Example 1

nums = [2, 3]
answer = [0, 2, 3, 5]           // {} , {2}, {3}, {2, 3}

Example 2

nums = [5, 2, 1]
answer = [0, 1, 2, 3, 5, 6, 7, 8]
// {} {1} {2} {1,2} {5} {5,1} {5,2} {5,2,1}

Example 3

nums = [3, 1, 2]
answer = [0, 1, 2, 3, 3, 4, 5, 6]   // 3 appears twice: from {3} and from {1, 2}

Approach 1: Brute force, build each subset from a bitmask

Intuition. A subset of n elements is an n-bit choice: bit i set means nums[i] is included. Counting from 0 to 2^n - 1 visits every subset exactly once, and for each one we add up the elements whose bit is set. The approach is simple and iterative, and for n ≤ 15 it is perfectly fast; its only waste is recomputing each sum from scratch, n operations per subset, even though the subset for mask and for mask + 1 share most of their elements.

Algorithm.

  1. For every mask from 0 to 2^n - 1:
  2. Sum nums[i] over the set bits i of mask and append the sum.
  3. Sort the list of sums and return it.
static List<Integer> bruteForce(int[] nums) {
    int n = nums.length;
    List<Integer> sums = new ArrayList<>();
    for (int mask = 0; mask < (1 << n); mask++) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) sum += nums[i];
        }
        sums.add(sum);
    }
    Collections.sort(sums);
    return sums;
}

Complexity. Time O(2^n · n) to compute the sums plus O(2^n · n) for sorting 2^n numbers (log 2^n = n). Space O(2^n) for the answer.

Approach 2: Optimal, pick / not-pick recursion with a running sum

Intuition. Instead of deciding all n bits and then summing, decide them one at a time and keep the partial sum as we go. At index i with running sum sum, the subsets of nums[i..] split into those that contain nums[i] (continue with sum + nums[i]) and those that do not (continue with sum). When the index reaches n, every element has been decided and sum is the sum of exactly one subset, so we record it. Each leaf now costs O(1) rather than O(n), and the recursion tree has 2^n leaves and 2^n - 1 internal nodes, so the total work is linear in the output size.

This is the standard subsequence recursion; it generates the subsets in a fixed order (the pick branch first), which is why the raw output is not sorted and a final sort is added for a canonical answer.

Algorithm.

  1. sumRec(i, sum): if i == n, append sum and return.
  2. Recurse with (i + 1, sum + nums[i]) (pick).
  3. Recurse with (i + 1, sum) (not pick).
  4. Start with sumRec(0, 0), then sort.
static List<Integer> optimal(int[] nums) {
    List<Integer> sums = new ArrayList<>();
    sumRec(nums, 0, 0, sums);
    Collections.sort(sums);
    return sums;
}

static void sumRec(int[] nums, int i, int sum, List<Integer> sums) {
    if (i == nums.length) {
        sums.add(sum);
        return;
    }
    sumRec(nums, i + 1, sum + nums[i], sums);   // pick nums[i]
    sumRec(nums, i + 1, sum, sums);             // leave nums[i] out
}

Dry run on nums = [2, 3]:

call (i, sum) branch result
(0, 0) pick 2 → (1, 2)  
(1, 2) pick 3 → (2, 5) leaf: record 5
(1, 2) not pick → (2, 2) leaf: record 2
(0, 0) not pick → (1, 0)  
(1, 0) pick 3 → (2, 3) leaf: record 3
(1, 0) not pick → (2, 0) leaf: record 0

Raw order [5, 2, 3, 0], sorted [0, 2, 3, 5].

Complexity. Time O(2^n) for the recursion plus O(2^n · n) if the final sort is required; without the sort it is strictly O(2^n). Space O(n) for the recursion stack, in addition to the O(2^n) output.

Approach 3: Iterative doubling

Intuition. The subsets of the first i + 1 elements are exactly the subsets of the first i elements, each either left alone or extended by nums[i]. So if S_i is the list of sums for the first i elements, then S_{i+1} is S_i followed by every value of S_i plus nums[i]. Starting from S_0 = [0] and applying this n times builds all 2^n sums with no recursion at all, and each new sum costs one addition. It is the same idea as the pick / not-pick tree, read level by level instead of depth first.

Algorithm.

  1. Start with sums = [0].
  2. For each x in nums: let size be the current length; for j in 0 .. size - 1, append sums[j] + x.
  3. Sort and return.
static List<Integer> iterative(int[] nums) {
    List<Integer> sums = new ArrayList<>();
    sums.add(0);                                 // the empty subset
    for (int x : nums) {
        int size = sums.size();
        for (int j = 0; j < size; j++) sums.add(sums.get(j) + x);
    }
    Collections.sort(sums);
    return sums;
}

Complexity. Time O(2^n) for the doubling (1 + 2 + 4 + ... + 2^(n-1) additions) plus the optional sort. Space O(2^n) for the output and nothing else; there is no recursion stack.

Capturing size before the inner loop matters: the list grows while we iterate, and reading sums.size() in the loop condition would never terminate.

If you need the subsets themselves

The sum is just one way to summarise a subset. The identical recursion, with a working list instead of a running sum, produces the subsets as lists; this is the Power Set problem, included here because the title of this entry is often read that way. Copy the working list at the leaf; storing cur itself would store a reference that later backtracking empties.

static List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> out = new ArrayList<>();
    subsetRec(nums, 0, new ArrayList<>(), out);
    return out;
}

static void subsetRec(int[] nums, int i, List<Integer> cur, List<List<Integer>> out) {
    if (i == nums.length) {
        out.add(new ArrayList<>(cur));
        return;
    }
    cur.add(nums[i]);                             // pick nums[i]
    subsetRec(nums, i + 1, cur, out);
    cur.remove(cur.size() - 1);                   // undo, then leave nums[i] out
    subsetRec(nums, i + 1, cur, out);
}

Time O(2^n · n) because each of the 2^n leaves copies a list of up to n elements. The test harness sums every generated subset and checks that the sorted result equals the three sum methods, so the four pieces of code are verified against each other.

Edge cases and pitfalls