PPractick

The problem

A board game gives each player a handful of number cards, and a special move lets them play any subset of their cards and score its total. To show a player every total they could possibly score, the game needs the sum of every one of the 2ⁿ subsets, including the empty subset (0), listed in increasing order. Equal totals from different subsets are listed separately. It's the pick/skip recursion, carrying only a running sum instead of the whole subset.

Example: [2, 3] → 0 2 3 5.

Function signature

vector<int> subsetSums(const vector<int>& arr);  // all 2^n sums, sorted ascending

Test cases

Input	Output	Explanation
[2, 3]	0 2 3 5	{}, {2}, {3}, {2, 3}
[5, 2, 1]	0 1 2 3 5 6 7 8	8 subsets
[3, 3]	0 3 3 6	The two single-card subsets both sum to 3
[1]	0 1
[]	0	Only the empty subset

(Confirm: all 2ⁿ sums are returned, repeats included; the output is sorted ascending; n is at most about 15.)

How interviewers phrase it

• "Given a list of n integers, return the sums of all its subsets in increasing order" (GeeksforGeeks "Subset Sums"; "Subsets I" in many recursion sheets).
• The LeetCode 78 version asks for the subsets themselves; it's the same recursion with a buffer instead of a running sum.

Clarifying questions to ask

1. Is the empty subset included (sum 0)? (Yes.)
2. Should equal sums from different subsets be repeated? (Yes, all 2ⁿ of them.)
3. What order should the output be in? (Increasing.)

Follow-ups to expect

1. "Why carry only the sum?"
2. "How many results?"
3. "Can you avoid the final sort?"
4. "What if you only needed the distinct sums?"
5. "Complexity?"

Related questions

• Generate Binary Strings Without Consecutive 1s Medium
• Generate Parentheses Medium
• Power Set Medium
• Combination Sum Medium
• Combination Sum II Medium
• Subsets II Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in