All Subset Sums
01 · Problem
Given an integer array nums of length n, consider every one of its 2^n subsets (choose any positions, including choosing none). Compute the sum of each subset; the empty subset has sum 0.
Return all 2^n sums in a single array sorted in non-decreasing order. Subsets with the same sum each contribute their own entry, so duplicate values are kept.
02 · Examples
nums = [2,3]
[0,2,3,5]
The subsets are [], [2], [3] and [2,3], with sums 0, 2, 3 and 5.
nums = [5,2,1]
[0,1,2,3,5,6,7,8]
The eight subsets give sums 0, 5, 2, 1, 7, 6, 3 and 8, which sorted are 0,1,2,3,5,6,7,8.
nums = [1,1]
[0,1,1,2]
Picking either 1 alone gives sum 1. These are different subsets (different positions), so 1 appears twice.
03 · Constraints
- 01`1 <= nums.length <= 15`
- 02`0 <= nums[i] <= 104`
- 03The output has exactly `2^n` elements, sorted in non-decreasing order
04 · Optimal complexity
- Time
- O(n * 2^n)
- Space
- O(2^n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.