DSA interview question

Power Set: All Subsets of an Array

Medium · Algorithms · Topics: recursion, backtracking

The problem

A pizza app lets customers pick any combination of toppings from a list of distinct toppings, including none at all. To pre-compute prices, the team needs every possible subset of the list, which is the power set. With n items there are 2ⁿ subsets, because each item is independently taken or not taken. The pick/skip recursion mirrors that exactly: at index i, branch once with nums[i] in the subset and once without it, and record the subset when the index reaches the end.

Example: [1, 2, 3] → [1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] [].

Function signature

vector<vector<int>> subsets(const vector<int>& nums);  // any order; shown in take-then-skip order

Test cases

Input	Output (take-then-skip order)	Explanation
`[1, 2, 3]`	`[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []`	2³ = 8 subsets
`[0]`	`[0] []`
`[1, 2]`	`[1,2] [1] [2] []`
`[]`	`[]`	Only the empty subset

(Confirm: elements are distinct; the empty subset is included; any order of subsets is acceptable.)

How interviewers phrase it

"Given an integer array of unique elements, return all possible subsets (the power set)" (LeetCode 78).

Clarifying questions to ask

Are the elements unique? (If not, see Subsets II.)
Does the order of subsets, or of elements within a subset, matter?
How large can n be? (About 10 to 20, since the output is 2ⁿ.)

Follow-ups to expect

"Why 2ⁿ subsets?"
"What does the recursion tree look like?"
"Other ways to generate them?"
"What if there are duplicates?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview