Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Subset Sums

MEDIUMProblemSolveExternal Links

Description

Given an array of integers arr, return a list containing the sums of all possible subsets of the array.

A subset is any selection of zero or more elements from the array. The empty subset (selecting no elements) has a sum of 0. You may return the sums in any order.

Examples

Example 1

Input: arr = [2, 3]

Output: [0, 2, 3, 5]

Explanation: There are 2² = 4 subsets of a 2-element array:

  • {} → sum = 0 (empty subset)
  • {2} → sum = 2
  • {3} → sum = 3
  • {2, 3} → sum = 2 + 3 = 5

So the output contains all four sums: [0, 2, 3, 5].

Example 2

Input: arr = [1, 2, 1]

Output: [0, 1, 1, 2, 2, 3, 3, 4]

Explanation: There are 2³ = 8 subsets:

  • {} → 0
  • {1} → 1 (first element)
  • {2} → 2
  • {1} → 1 (third element)
  • {1, 2} → 3
  • {1, 1} → 2
  • {2, 1} → 3
  • {1, 2, 1} → 4

Note that duplicate sums appear because elements at different positions can produce the same sum.

Example 3

Input: arr = [5, 6, 7]

Output: [0, 5, 6, 7, 11, 12, 13, 18]

Explanation: All 8 subsets and their sums:

  • {} → 0
  • {5} → 5
  • {6} → 6
  • {7} → 7
  • {5, 6} → 11
  • {5, 7} → 12
  • {6, 7} → 13
  • {5, 6, 7} → 18

Constraints

  • 1 ≤ arr.size() ≤ 15
  • 0 ≤ arr[i] ≤ 10^4

Editorial

Brute Force

Intuition

Every subset of an array can be represented by a binary number. If the array has n elements, there are exactly 2ⁿ subsets. We can map each integer from 0 to 2ⁿ - 1 to a unique subset by looking at its binary representation: if the j-th bit is 1, we include arr[j] in the subset; if it's 0, we exclude it.

Think of it like a row of n light switches. Each switch corresponds to one element. Every possible combination of on/off switches represents a different subset. There are 2ⁿ combinations, so we just flip through all of them and compute the sum for each combination.

For example, with arr = [2, 3]:

  • Binary 00 → include nothing → sum = 0
  • Binary 01 → include arr[0]=2 → sum = 2
  • Binary 10 → include arr[1]=3 → sum = 3
  • Binary 11 → include both → sum = 5

Step-by-Step Explanation

Let's trace through with arr = [2, 3] (n = 2, so total = 2² = 4 masks):

Step 1: Initialize the result list as empty. We will iterate through mask values 0 to 3.

Step 2: mask = 0 (binary: 00).

  • Bit 0 is 0 → skip arr[0]=2.
  • Bit 1 is 0 → skip arr[1]=3.
  • Sum = 0. Append 0 to result.

Step 3: mask = 1 (binary: 01).

  • Bit 0 is 1 → include arr[0]=2.
  • Bit 1 is 0 → skip arr[1]=3.
  • Sum = 2. Append 2 to result.

Step 4: mask = 2 (binary: 10).

  • Bit 0 is 0 → skip arr[0]=2.
  • Bit 1 is 1 → include arr[1]=3.
  • Sum = 3. Append 3 to result.

Step 5: mask = 3 (binary: 11).

  • Bit 0 is 1 → include arr[0]=2.
  • Bit 1 is 1 → include arr[1]=3.
  • Sum = 2 + 3 = 5. Append 5 to result.

Step 6: All masks processed. Result = [0, 2, 3, 5].

Bit Masking — Enumerating All Subsets — Watch how each integer from 0 to 2ⁿ-1 acts as a bitmask, selecting which elements to include in the current subset sum.

Algorithm

  1. Compute total = 2ⁿ (the number of subsets).
  2. For each mask from 0 to total - 1:
    a. Initialize sum = 0.
    b. For each bit position j from 0 to n - 1:
    • If the j-th bit of mask is set (mask & (1 << j) is non-zero), add arr[j] to sum.
      c. Append sum to the result list.
  3. Return the result list.

Code

class Solution {
public:
    vector<int> subsetSums(vector<int>& arr) {
        int n = arr.size();
        int total = 1 << n;
        vector<int> result;
        
        for (int mask = 0; mask < total; mask++) {
            int sum = 0;
            for (int j = 0; j < n; j++) {
                if (mask & (1 << j)) {
                    sum += arr[j];
                }
            }
            result.push_back(sum);
        }
        
        return result;
    }
};
class Solution:
    def subsetSums(self, arr):
        n = len(arr)
        total = 1 << n
        result = []
        
        for mask in range(total):
            current_sum = 0
            for j in range(n):
                if mask & (1 << j):
                    current_sum += arr[j]
            result.append(current_sum)
        
        return result
class Solution {
    public ArrayList<Integer> subsetSums(int[] arr) {
        int n = arr.length;
        int total = 1 << n;
        ArrayList<Integer> result = new ArrayList<>();
        
        for (int mask = 0; mask < total; mask++) {
            int sum = 0;
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) != 0) {
                    sum += arr[j];
                }
            }
            result.add(sum);
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n × 2ⁿ)

We iterate through 2ⁿ masks. For each mask, we check all n bits to determine which elements to include. This gives us n operations per mask, totaling n × 2ⁿ operations.

Space Complexity: O(2ⁿ)

The result list stores one sum per subset, giving exactly 2ⁿ entries. Beyond the output, we only use a constant number of extra variables (mask, sum, j).

Why This Approach Is Not Efficient

The bit-masking approach runs in O(n × 2ⁿ) time. While the 2ⁿ subsets are unavoidable (we must produce all of them), the extra factor of n comes from scanning every bit position for each mask.

For each mask, we re-compute the sum from scratch by iterating through all n elements. This is redundant — when we move from mask 5 (binary 101) to mask 6 (binary 110), only one or two elements change, yet we sum everything from zero again.

Can we do better? If we use recursion with the include/exclude pattern, each element is processed exactly once per recursive branch, and we carry a running sum. This eliminates the inner loop, bringing the time down to O(2ⁿ) — a factor of n improvement.

Optimal Approach - Recursion (Include / Exclude)

Intuition

For every element in the array, we have exactly two choices: either include it in the current subset or exclude it. This naturally forms a binary decision tree.

Imagine you're packing a bag with n items on a table. You stand at the first item and decide: put it in the bag, or leave it. Then you move to the second item and make the same decision, and so on. Once you've decided for every item, the bag represents one complete subset.

The key insight is that we carry a running sum as we make decisions. When we include an element, we add its value to the running sum. When we exclude it, the running sum stays the same. When we've processed all elements (reached the end of the array), the running sum IS the subset sum — no separate summation loop needed.

This divide-and-conquer approach generates all 2ⁿ subsets naturally: at each of the n levels of recursion, we branch into two paths. The total number of leaf nodes (completed subsets) is exactly 2ⁿ.

Step-by-Step Explanation

Let's trace through with arr = [2, 3] using recursive include/exclude:

Step 1: Start the recursion with index = 0 and sum = 0.

Step 2: At index 0 (element 2), choose to INCLUDE it. New sum = 0 + 2 = 2. Recurse with index = 1, sum = 2.

Step 3: At index 1 (element 3) on the include-2 branch, choose to INCLUDE it. New sum = 2 + 3 = 5. Recurse with index = 2, sum = 5.

Step 4: Index 2 exceeds array bounds (base case). Record sum = 5 into result. Backtrack.

Step 5: Back at index 1 on the include-2 branch, now choose to EXCLUDE element 3. Sum stays 2. Recurse with index = 2, sum = 2.

Step 6: Index 2 exceeds bounds (base case). Record sum = 2 into result. Backtrack.

Step 7: Back at index 0, now choose to EXCLUDE element 2. Sum stays 0. Recurse with index = 1, sum = 0.

Step 8: At index 1 (element 3) on the exclude-2 branch, choose to INCLUDE it. New sum = 0 + 3 = 3. Recurse with index = 2, sum = 3.

Step 9: Base case. Record sum = 3 into result. Backtrack.

Step 10: At index 1 on the exclude-2 branch, choose to EXCLUDE element 3. Sum stays 0. Recurse with index = 2, sum = 0.

Step 11: Base case. Record sum = 0 into result. Backtrack.

Step 12: All branches explored. Result = [5, 2, 3, 0].

Recursive Include/Exclude — Building All Subset Sums — Watch the binary decision tree unfold: at each level, we either include or exclude the current element, carrying a running sum to each leaf.

Algorithm

  1. Create a helper function solve(index, currentSum, result).
  2. Base case: If index equals the array length, append currentSum to result and return.
  3. Include choice: Call solve(index + 1, currentSum + arr[index], result) — this picks arr[index] into the subset.
  4. Exclude choice: Call solve(index + 1, currentSum, result) — this skips arr[index].
  5. Start the recursion with solve(0, 0, result).
  6. Return the result list.

Code

class Solution {
public:
    void solve(vector<int>& arr, int index, int currentSum, vector<int>& result) {
        if (index == arr.size()) {
            result.push_back(currentSum);
            return;
        }
        // Include arr[index]
        solve(arr, index + 1, currentSum + arr[index], result);
        // Exclude arr[index]
        solve(arr, index + 1, currentSum, result);
    }
    
    vector<int> subsetSums(vector<int>& arr) {
        vector<int> result;
        solve(arr, 0, 0, result);
        return result;
    }
};
class Solution:
    def subsetSums(self, arr):
        result = []
        
        def solve(index, current_sum):
            if index == len(arr):
                result.append(current_sum)
                return
            # Include arr[index]
            solve(index + 1, current_sum + arr[index])
            # Exclude arr[index]
            solve(index + 1, current_sum)
        
        solve(0, 0)
        return result
class Solution {
    private void solve(int[] arr, int index, int currentSum, ArrayList<Integer> result) {
        if (index == arr.length) {
            result.add(currentSum);
            return;
        }
        // Include arr[index]
        solve(arr, index + 1, currentSum + arr[index], result);
        // Exclude arr[index]
        solve(arr, index + 1, currentSum, result);
    }
    
    public ArrayList<Integer> subsetSums(int[] arr) {
        ArrayList<Integer> result = new ArrayList<>();
        solve(arr, 0, 0, result);
        return result;
    }
}

Complexity Analysis

Time Complexity: O(2ⁿ)

The recursion tree has exactly 2ⁿ leaf nodes (one for each subset). Each internal node does O(1) work — just a single addition and two recursive calls. The total number of nodes in the tree is 2^(n+1) - 1, which is O(2ⁿ). Unlike the bitmask approach, there is no inner loop iterating over n bits; the running sum is maintained incrementally.

Space Complexity: O(n) (excluding the output)

The recursion stack goes at most n levels deep (one level per element). Each stack frame stores only a constant amount of data (index, currentSum). The output list takes O(2ⁿ) space, but that is required by the problem and not counted as auxiliary space. So the auxiliary space for the recursion is O(n).