Subset sums (all possible sums of subsets)
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]
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);}