DSA interview question

Power Set Using Bit Manipulation

Medium · Algorithms · Topics: bit manipulation

The problem

A test harness must run a service under every combination of n feature flags, from all off to all on. Instead of recursion, it counts: every integer mask from 0 to 2ⁿ − 1 is one combination, where bit i of the mask says whether flag i is on. Looping over the masks and decoding each one lists the whole power set with no recursion stack, in a predictable order: [], [a], [b], [a, b], [c], …

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

Function signature

vector<vector<int>> subsets(const vector<int>& nums);  // in mask order 0 .. 2^n - 1

Test cases

Input	Output (mask order)	Explanation
`[1, 2, 3]`	`[] [1] [2] [1,2] [3] [1,3] [2,3] [1,2,3]`	Masks 000 to 111
`[0]`	`[] [0]`
`[5, 9]`	`[] [5] [9] [5,9]`
`[]`	`[]`	2⁰ = 1 subset

(Confirm: elements are distinct; n ≤ 20 so that 2ⁿ fits comfortably; any order is acceptable, mask order is shown.)

How interviewers phrase it

"Return all subsets of an array" (LeetCode 78), with "can you do it without recursion, using bits?" as the follow-up.

Clarifying questions to ask

Are elements distinct? (With duplicates, see Subsets II.)
How large can n be? (The output is 2ⁿ, so n ≤ 20 or so.)
Does order matter?

Follow-ups to expect

"Why is there a one-to-one correspondence?"
"How do you decode a mask?"
"Can you iterate only the subsets of a given mask?"
"Recursion or bitmask: which is better?"
"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