350. Subset Sums

Given an array of n integers, print the sums of all 2^n possible subsets (including the empty subset, which sums to 0), sorted in non-decreasing order. If two different subsets happen to have the same sum, print that sum once for each of them.

Input: The first line contains an integer n. The second line contains n space-separated integers. Output: Print all 2^n subset sums, sorted in non-decreasing order, space-separated on one line.

1 <= n <= 15

The small constraint (n <= 15, giving at most 32768 subsets) is a strong signal that the expected approach is this direct exponential enumeration, not some cleverer polynomial trick - recognizing constraint size as a hint toward expected complexity is a valuable skill.

Print the sums of every possible subset of an array, including the empty subset. Brute force: There isn't really a 'slower' alternative distinct from this recursive enumeration - generating all 2^n subset sums IS inherently exponential work, since the problem asks for every one of them. Optimised: The recursive include/exclude branching generates each of the 2^n subset sums exactly once, with no redundant recomputation - each recursive call simply carries forward a running sum, avoiding the need to re-sum a subset from scratch every time.

Start with a list containing just the sum 0 (the empty subset). For each array element x in turn, append (existing_sum + x) for every sum currently in the list to the end of the list itself - this doubles the list's length with each element processed, and after all n elements it contains exactly all 2^n subset sums, generated with no recursion or function-call overhead at all. Sort this final list once to produce the required non-decreasing order. This is fully iterative and cache-friendly, generating all sums with a simple loop-based doubling instead of recursive branching, while remaining asymptotically dominated by the same final sort. Time: O(2^n log(2^n)) Space: O(2^n)

Use the same include/exclude recursion, but thread the running sum as a parameter that is incremented or left alone at each recursive call instead of being recomputed from the full subset at the end - so reaching a leaf (a decision made for every element) costs only O(1) extra work rather than O(n). Collect all 2^n sums this way, then sort them once. This removes the redundant re-summation of the brute-force approach, so the sort at the end becomes the dominant cost. Time: O(2^n log(2^n)) Space: O(2^n)

Recursively build every one of the 2^n subsets explicitly by including or excluding each element, and at each leaf of the recursion (a complete subset), sum up all of its chosen elements from scratch, then sort the collected list of sums at the end. This correctly enumerates every subset, but recomputing each subset's sum by adding up all of its elements independently means the summing work itself scales with both the subset size and the number of subsets. Time: O(n * 2^n) Space: O(2^n)

1. Recurse on each element in turn, branching into two choices: INCLUDE it in the running sum, or EXCLUDE it. 2. When you've made a decision for every element, record the running sum as one of the 2^n subset sums. 3. Sort the final list of all 2^n sums before printing (without deduplicating repeats).

Time: O(2^n), since there are exactly 2^n subsets to generate, though the small constraint (n <= 15) keeps this entirely manageable. Space: O(2^n) to store all generated sums, plus O(n) for the recursion depth.

Test n = 1 (two sums: 0 and the element), duplicate sums from different subsets (all printed, not deduplicated), and n = 15 (largest case, 32768 sums).

Be ready to point out that this DOESN'T deduplicate repeated sums (unlike a similar-sounding 'distinct subset sums' variant) - the problem explicitly asks for a sum to be printed once per subset that achieves it, even if multiple subsets tie.