☕ DSA Java Articles

Topics › Recursion and Backtracking › Subsequences Pattern

Subset Sums

Hard TUF ID 2805 SDE

Java source ↗ Edit this article ↗

Problem

Given an array arr of n integers, return the sum of every one of its 2^n subsets, in non-decreasing order. A subset may be empty (its sum is 0) and may be the whole array. Subsets are chosen by position, so if two subsets happen to have the same sum, that sum appears twice in the output.

Constraints: 1 ≤ n ≤ 15, 0 ≤ arr[i] ≤ 10^4. The output alone has 2^15 = 32 768 numbers, so any method is at least exponential; the question is how much work we spend per subset. We also accept an empty array (the only subset is empty) and negative values.

Example 1

arr = [2, 3]
subsets: {} {2} {3} {2,3}
answer = [0, 2, 3, 5]

Example 2

arr = [5, 2, 1]
answer = [0, 1, 2, 3, 5, 6, 7, 8]     // 8 = 2^3 sums, here all different

Approach 1: Brute force, enumerate subsets as bitmasks

Intuition. A subset of n elements is a yes/no decision for each element, which is exactly an n-bit number: bit i set means “arr[i] is in”. So the integers 0 to 2^n - 1 list every subset exactly once. For each mask, add up the elements whose bits are set, collect the sums, and sort.

Algorithm.

  1. For every mask from 0 to 2^n - 1:
  2. Sum arr[i] over all i with bit i set in mask; append the sum.
  3. Sort the collected sums and return them.
static List<Integer> bitmask(int[] arr) {
    int n = arr.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 += arr[i];   // bit i set: arr[i] is in this subset
        }
        sums.add(sum);
    }
    Collections.sort(sums);
    return sums;
}

Complexity. Time O(n × 2^n): every mask inspects all n bits, and sorting 2^n values costs O(2^n × log 2^n) = O(n × 2^n) as well. Space O(2^n) for the output.

The inefficiency is that neighbouring subsets share most of their elements, yet every mask recomputes its sum from scratch.

Approach 2: Better, pick / not-pick recursion

Intuition. Build subsets one decision at a time. At index i there are two branches: include arr[i] or skip it. Carry the running sum down the recursion, so that when all n decisions are made (index == n), the sum of that subset is already known. The recursion tree has 2^n leaves, one per subset, and each leaf costs O(1) instead of O(n).

For arr = [2, 3] the tree is:

                    (index 0, sum 0)
            pick 2 /                \ skip 2
      (index 1, sum 2)            (index 1, sum 0)
    pick 3 /      \ skip 3      pick 3 /      \ skip 3
         5          2                3          0

The leaves produce 5, 2, 3, 0, which sort to 0, 2, 3, 5.

Algorithm.

  1. Call collect(arr, 0, 0, sums).
  2. In collect: if index == n, append sumSoFar and return. Otherwise recurse with sumSoFar + arr[index] (pick) and with sumSoFar (skip), both at index + 1.
  3. Sort sums and return it.
static List<Integer> recursion(int[] arr) {
    List<Integer> sums = new ArrayList<>();
    collect(arr, 0, 0, sums);
    Collections.sort(sums);
    return sums;
}

static void collect(int[] arr, int index, int sumSoFar, List<Integer> sums) {
    if (index == arr.length) {                      // every element has been decided: one subset done
        sums.add(sumSoFar);
        return;
    }
    collect(arr, index + 1, sumSoFar + arr[index], sums);   // pick arr[index]
    collect(arr, index + 1, sumSoFar, sums);                // skip arr[index]
}

Complexity. Time O(2^n) to generate (the tree has about 2^(n+1) nodes, each doing constant work), plus O(n × 2^n) for the final sort, so O(n × 2^n) overall. Space O(n) for the recursion depth, plus O(2^n) for the output.

This is the expected interview answer, and the pick / not-pick pattern it uses is the backbone of every subset and subsequence problem. But the sort now dominates the running time. Can we produce the sums already in order?

Approach 3: Optimal, keep the sums sorted while building them

Intuition. Suppose S is the sorted list of subset sums of the first i elements. Adding element x doubles the subsets: each old subset either stays as it is (sum unchanged) or gains x (sum plus x). So the new list consists of S and S + x, where S + x adds x to every element. Both lists are sorted, because adding the same constant to every element does not change their order. Two sorted lists merge into one sorted list in linear time, the same merge used in merge sort. No sort is ever needed.

Algorithm.

  1. Start with sums = [0], the subset sums of the empty prefix.
  2. For each x in arr: merge sums with sums + x into a new array of twice the length, and make it the new sums.
  3. Return sums as a list.
static List<Integer> sortedMerge(int[] arr) {
    int[] sums = new int[]{0};                      // sums of all subsets of an empty prefix
    for (int x : arr) {
        int m = sums.length;
        int[] next = new int[2 * m];
        int i = 0, j = 0, w = 0;                    // i walks "without x", j walks "with x"
        while (i < m && j < m) {
            if (sums[i] <= sums[j] + x) next[w++] = sums[i++];
            else next[w++] = sums[j++] + x;
        }
        while (i < m) next[w++] = sums[i++];
        while (j < m) next[w++] = sums[j++] + x;
        sums = next;
    }
    List<Integer> out = new ArrayList<>(sums.length);
    for (int s : sums) out.add(s);
    return out;
}

Dry run on Example 2 ([5, 2, 1]):

x sums sums + x merged
start     0
5 0 5 0 5
2 0 5 2 7 0 2 5 7
1 0 2 5 7 1 3 6 8 0 1 2 3 5 6 7 8

The merge never materialises sums + x as a separate array; index j walks sums a second time and adds x on the fly.

Complexity. Time O(2^n): the merges cost 2 + 4 + ... + 2^n < 2^(n+1). Since the output itself has 2^n numbers, no algorithm can do asymptotically better. Space O(2^n) for the current and next arrays.

Edge cases and pitfalls