Subset sums (all possible sums of subsets)

Easy

Problem

Return the sums of all 2^n subsets of the array (including the empty subset, which sums to 0), in any order or sorted.

Example 1

Input:  [2, 3]
Output: [0, 2, 3, 5]

Also asked as: Subset Sums

Test cases

Case 1

Input:    [2,3]
Expected (any order): [0,2,3,5]

Case 2

Input:    [5,2,1]
Expected (any order): [0,1,2,3,5,6,7,8]

Case 3

Input:    [1,1]
Expected (any order): [0,1,1,2]

Case 4

Input:    []
Expected (any order): [0]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Recurse: include / exclude each element

Time O(2ⁿ)Space O(n) recursion

At each index branch on taking the element into the running sum or not; record the sum at the leaves.

function subsetSums(a) {
const res = [];
const bt = (i, sum) => {
if (i === a.length) { res.push(sum); return; }
bt(i + 1, sum + a[i]);
bt(i + 1, sum);
};
bt(0, 0);
return res.sort((x, y) => x - y);
}