Subsets (Power Set) in Coding Interviews: Three Ways to Generate Every Combination
3 views
"Given a set of distinct integers, return all possible subsets" is a short problem that interviewers use to check whether you understand recursion, iteration and bit manipulation. For n elements there are 2^n subsets, so any correct solution is at least O(n * 2^n) in time, because that is the size of the output.
Approach 1: Iterative building
Start with the empty subset. For each number, copy every existing subset and add the number to the copy.
def subsets(nums):
res = [[]]
for x in nums:
res += [s + [x] for s in res]
return res
For [1, 2, 3]: [[]] becomes [[], [1]], then [[], [1], [2], [1, 2]], then all eight. It is short, easy to explain, and a good first answer.
Approach 2: Backtracking
At each index, decide to include or skip the element, or equivalently, loop over the remaining elements and extend the current path.
def subsets_bt(nums):
res, path = [], []
def dfs(start):
res.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
dfs(i + 1)
path.pop()
dfs(0)
return res
Copy the path with path[:] when recording it; appending the same list object is the most common bug. This template generalizes to combinations, combination sum and permutations, which is why interviewers like it.
Approach 3: Bit masks
Each subset corresponds to an n-bit number: bit j set means nums[j] is included.
def subsets_bits(nums):
n = len(nums)
return [[nums[j] for j in range(n) if mask >> j & 1] for mask in range(1 << n)]
This is elegant and avoids recursion, but it is limited to n small enough that 2^n fits in memory, which is true for any problem asking you to list all subsets anyway.
The duplicates follow-up (Subsets II)
If nums can contain duplicates, such as [1, 2, 2], the answer must not include [1, 2] twice. Sort first, then in the backtracking loop skip an element equal to the previous one at the same depth:
if i > start and nums[i] == nums[i - 1]:
continue
Explain why the condition is i > start and not i > 0: you still want to use the second 2 after choosing the first one, just not start a new branch with it at the same level.
Other follow-ups
1. Subsets of size k: stop recursing when the path length reaches k (combinations).
2. Count subsets with a given sum: this becomes a dynamic programming problem when n is large.
3. Lexicographic order: sort the input and use backtracking.
4. Iterator version: generate subsets lazily with a generator or mask counter to save memory.
How to present it
Start with the output-size argument, pick one approach and code it cleanly, then mention the others and their trade-offs. Showing that you know three angles on the same problem signals real understanding.
If recursion questions make your mind go blank in a live round, Linkjob AI (https://linkjob.ai) gives real-time help during job interviews and technical interviews, helping you stay structured while you explain and code.