← Create New Paste

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.
Created Nov 17, 2026 12:02 Expires Nov 17, 2027 12:02