Subset Sums

New·Easy·Recursion

Total of every subset, via include / exclude

Asked at:AmazonMicrosoftAdobe

Practice mode

Step

Initialization

Branch include / exclude at every index, adding the element to a running sum on the include side. When the index runs out, that sum is one subset's total — there are exactly 2ⁿ of them, duplicates included.

Recursion workspace

Include / Exclude

Step 1 / 38init

100%

nums

[1,2,3]

picked

[]

sum

[]Σ 0

each level decides one element — left branch includes it (sum + nums[i]), right branch excludes it; every leaf is one subset's total

ans

empty

Explanation

Only the running sum is carried down — the subset itself is never stored. Including an element adds it to the sum; excluding leaves the sum unchanged.

step 1 / 38

Space play← → stepHome reset

TimeO(2ⁿ)·SpaceO(n)

Include / Exclude

1function subsetSums(nums) {
2  function func(ind, sum, nums, ans) {
3    // Base case: every element decided
4    if (ind === nums.length) {
5      ans.push(sum);
6      return;
7    }
8 
9    // Include nums[ind] in the running sum
10    func(ind + 1, sum + nums[ind], nums, ans);
11 
12    // Exclude it
13    func(ind + 1, sum, nums, ans);
14  }
15 
16  const ans = [];
17  func(0, 0, nums, ans);//n: 3
18  return ans;
19}

Command Palette

Subset Sums

Subset Sums