Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Return the power set — every subset of a distinct-element array. The canonical answer is backtracking with a start index where you record the path at EVERY node (not just leaves), because every partial path is itself a valid subset. Choose `nums[i]`, recurse with `i + 1` (each element used at most once), then un-choose. There are exactly 2ⁿ subsets, so any correct solution is O(2ⁿ).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognise that every node of the recursion tree is a valid subset (so you record everywhere, not just at leaves), and whether you control the start index to avoid duplicates. Bonus: knowing the bitmask alternative and that 2ⁿ is a hard lower bound.
Where candidates slip
Only recording at the leaves (giving subsets of one fixed size instead of all), passing `i` instead of `i + 1` (allowing reuse), or storing the live `path` reference so all results mutate to the same list.
How to stand out
State that the answer size is exactly 2ⁿ so O(2ⁿ) is optimal, show the choose/explore/un-choose recursion, then offer the bitmask iterative version as a clean O(2ⁿ · n) alternative with no recursion stack.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Every node — not just the leaves — is a subset that gets recorded. Each edge is a 'choose'; returning up the tree is an 'un-choose'. The loop only moves forward (start index), so {2,1} or {3,1} never appear.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
Backtracking with Start Index (Optimal)
1Hint 1Explore hintHide hint
There are 2ⁿ subsets because each element is independently in or out. Can you grow a subset one element at a time, branching on 'take this element' vs 'skip it'?
2Hint 2Explore hintHide hint
Use a `start` index and loop `i` from `start`. 'Choose' nums[i] (append), recurse from `i + 1`, then 'un-choose' (pop). What's different from Combination Sum is when you record an answer.
3Hint 3Explore hintHide hint
Unlike a sum-target problem, there's no condition to wait for — every partial path is already a valid subset. So record the path at the TOP of every call, before the loop.
A · Core idea
Grow a subset one element at a time. At each call, first record the current path (it's a complete, valid subset on its own), then loop i from start to the end: choose nums[i] by appending it, explore by recursing from i + 1, then un-choose by popping it. The recursion bottoms out naturally when the loop has no more elements to add.
Why we record at every node, not just at leaves. This is the one idea that separates Subsets from constraint problems like Combination Sum. There, an answer is only valid when the running sum hits the target, so you record only at qualifying leaves. Here there is no constraint — the empty set, every singleton, every pair, and the full array are all legitimate subsets. Each node of the recursion tree corresponds to exactly one subset (the elements chosen on the path from the root), so recording at the top of every call captures all 2ⁿ of them, including the empty set at the root.
Why recurse with `i + 1` and not `i`. Passing i + 1 means the next level can only consider elements after the one we just picked, so each element is used at most once — which is what makes these subsets rather than multisets. If you passed i (as Combination Sum does for reuse), you'd generate [1,1], [1,1,1], and so on. The single-character difference between i and i + 1 is the lever that flips 'reuse allowed' to 'each element once' — name it explicitly in the interview.
Why the loop starts at `start`, never 0. Starting at start enforces that subsets are always built in increasing index order, so we generate {1,2} but never {2,1}. Without it, the same subset would appear in multiple orderings and the result would contain duplicates. Combined with i + 1, the start index guarantees each subset is produced exactly once.
Why the un-choose (pop) and the copy both matter. path is a single shared list threaded through the entire tree. After exploring the branch that picked nums[i], we pop() it so the next sibling iteration starts from the correct prefix — skip the pop and choices bleed across branches. And when we record, we append path[:] (a snapshot); appending the live path stores a reference that subsequent pops mutate, leaving every stored subset corrupted.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [1, 2, 3]Interactive diagram
Choose / explore / un-choose for [1,2,3]
start=0, path=[]Going down an edge is a 'choose'; coming back up is an 'un-choose'. The path at every node is recorded as a subset, so all 8 nodes are answers.
[[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]C · Code with teaching comments
D · Why it works and complexityO(n · 2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Subsets is the degenerate case of the backtracking family where the 'constraint' is trivially always satisfied. That's why you record at every node instead of only at qualifying leaves. Once you see subsets as 'a binary in/out decision per element', Combinations (fix the size), Subsets II (skip duplicate siblings), and Permutations (track used instead of a start index) are all small edits to this same skeleton.
ComplexityO(n · 2ⁿ) time, O(n) space — There are 2ⁿ subsets and the recursion visits exactly 2ⁿ nodes (one per subset). At each node we copy the path, which costs up to O(n). So total work is O(n · 2ⁿ) time. Excluding the output, extra space is just the recursion depth and the live path, both O(n).
E · Edge cases and pitfalls5nums = [0] — Records [] at the root, then chooses 0 and records [0]. Returns [[], [0]] — confirms 0 as an element causes no truthiness issue since we never test the value.Explore edge casesHide edge cases
Edge cases handled
nums = [0]Records [] at the root, then chooses 0 and records [0]. Returns [[], [0]] — confirms 0 as an element causes no truthiness issue since we never test the value.nums = [1]Root records [], the single iteration records [1]. Returns [[], [1]] — the minimal 2¹ = 2 subsets.
Pitfalls
- Recording only at leaves (e.g. `if start == nums.length`) — yields only the single full subset instead of all 2ⁿ.
- Passing `i` instead of `i + 1` — allows reuse and produces multisets like [1,1].
- Appending `path` instead of `path[:]` / `new ArrayList<>(path)` — every stored subset mutates to the same final list.
Approach 2 of 2
Bitmask Enumeration (Iterative)
1Hint 1Explore hintHide hint
Each element is independently in or out — that's exactly one bit per element. How many distinct n-bit numbers are there?
2Hint 2Explore hintHide hint
Iterate an integer `mask` from 0 to 2ⁿ − 1. Each value of mask is one subset; the set bits tell you which elements to include.
3Hint 3Explore hintHide hint
For each mask, scan bits 0..n−1: if bit i is set (`mask & (1 << i)`), include nums[i]. No recursion, no path to copy back.
A · Core idea
Every subset corresponds one-to-one with a choice of 'in or out' for each of the n elements — which is precisely an n-bit binary number. So we can skip recursion entirely: iterate mask over every integer from 0 to 2ⁿ − 1, and for each one, read its bits to decide which elements to include.
Why this is exactly equivalent to backtracking. The recursion tree has 2ⁿ leaves-worth of subsets because each level makes a binary include/exclude decision. A bitmask collapses those decisions into the bits of a single integer: bit i set means 'element i is in this subset'. Counting mask from 0 upward enumerates every combination of those bits, hence every subset — mask = 0 is the empty set and mask = 2ⁿ − 1 (all bits set) is the full array.
Why `mask & (1 << i)` is the membership test. (1 << i) is an integer with only bit i set. ANDing it with mask isolates that single bit: the result is non-zero exactly when element i is included. Looping i from 0 to n−1 and including nums[i] whenever the test passes reconstructs the subset for that mask.
When to prefer this over recursion. The bitmask version has no recursion stack (O(1) extra space) and is often faster in practice due to tight integer loops and no call overhead. Its limit is that it only works while 2ⁿ fits comfortably — for n up to ~20–30 it's fine, and this problem caps n at 10. For problems with constraints or pruning (Combination Sum, N-Queens), recursion is the natural fit; for pure power-set enumeration of small n, the bitmask is elegant.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [1, 2, 3]mask=000
no bits set
subset = [][[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]C · Code with teaching comments
Reference implementation previewpublic List<List<Integer>> subsets(int[] nums) { int n = nums.length; List<List<Integer>> results = new ArrayList<>(); for (int mask = 0; mask < (1 << n); mask++) { // every n-bit number = one subset List<Integer> subset = new ArrayList<>();Explore the full codeHide the full code
D · Why it works and complexityO(n · 2ⁿ) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The bijection 'subset ↔ n-bit integer' is worth internalising: it turns enumeration of all subsets into a simple counting loop, and it's the basis for bitmask dynamic programming (Travelling Salesman, assignment problems) where a state IS a subset packed into an int.
ComplexityO(n · 2ⁿ) time, O(1) space — The outer loop runs 2ⁿ times (one per mask); the inner loop scans n bits each time, so total time is O(n · 2ⁿ). Apart from the output list, only a constant number of integer variables are used — O(1) extra space (no recursion stack).
E · Edge cases and pitfalls5nums = [0] — n=1, masks 0 and 1. mask=0 → [], mask=1 (bit 0 set) → [0]. Value 0 is fine because we test the bit, not the value.Explore edge casesHide edge cases
Edge cases handled
nums = [0]n=1, masks 0 and 1. mask=0 → [], mask=1 (bit 0 set) → [0]. Value 0 is fine because we test the bit, not the value.nums = [1, 2]n=2, masks 0..3 → [], [1], [2], [1,2]. Confirms 2² = 4 subsets in mask order.
Pitfalls
- Writing `1 << n` as `int` when n could overflow — fine here (n ≤ 10), but for n ≥ 31 use `1L << n`.
- Confusing bit index with element value — bit i selects nums[i], not the number i.
- Using `mask & (1 << i)` directly as a boolean in languages where it returns the bit value — in Java compare `!= 0`; in Python it's truthy as-is.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic List<List<Integer>> subsets(int[] nums) { List<List<Integer>> results = new ArrayList<>(); backtrack(nums, 0, new ArrayList<>(), results); return results; }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Recording only at leaves
If you only append when `start == nums.length`, you capture a single subset (the full array) and miss the empty set, singletons, and every intermediate subset. The whole point is that EVERY node is a subset.
Explore the code comparisonHide the code comparison
Recording only at leaves
If you only append when `start == nums.length`, you capture a single subset (the full array) and miss the empty set, singletons, and every intermediate subset. The whole point is that EVERY node is a subset.
Don't write this
def backtrack(start, path):
if start == len(nums):
results.append(path[:]) # only the full subset!
return
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()Write this instead
def backtrack(start, path):
results.append(path[:]) # record at EVERY node
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()2Passing i instead of i + 1 (allows reuse)
Recursing with `i` lets the same element be chosen again at the next level, producing multisets like [1,1] and [1,1,1]. Subsets use each element at most once, so recurse with `i + 1`.
Explore the code comparisonHide the code comparison
Passing i instead of i + 1 (allows reuse)
Recursing with `i` lets the same element be chosen again at the next level, producing multisets like [1,1] and [1,1,1]. Subsets use each element at most once, so recurse with `i + 1`.
Don't write this
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i, path) # reuse → multisets, wrong
path.pop()Write this instead
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path) # each element at most once
path.pop()3Storing the live path reference
`results.append(path)` stores the same list object; subsequent pops mutate it, so all results collapse to the same (often empty) list. Append a snapshot.
Explore the code comparisonHide the code comparison
Storing the live path reference
`results.append(path)` stores the same list object; subsequent pops mutate it, so all results collapse to the same (often empty) list. Append a snapshot.
Don't write this
results.append(path) # reference to a mutating listWrite this instead
results.append(path[:]) # snapshot copyRevise
Carry the pattern into the interview
Pattern to remember
Backtracking with a start index, recording every node (choose → explore → un-choose)
Code pattern to memorize
def backtrack(start, path):
results.append(path[:]) # record EVERY node — each path is a subset
for i in range(start, len(nums)):
path.append(nums[i]) # choose
backtrack(i + 1, path) # explore, i+1 → each element at most once
path.pop() # un-chooseRules to remember
- 1Record the path at every node, not only at the leaves — unlike Combination Sum, there's no target to hit; every partial path is a valid subset.
- 2Recurse with
i + 1(noti) so each element is used at most once — passingiwould allow reuse and produce multisets. - 3Loop from
start, never0— the never-go-backward rule emits subsets in index order and prevents duplicates like {1,2} and {2,1}. - 4Append a copy
path[:]— the live list is mutated by later pops and would corrupt every stored subset. - 5There are exactly 2ⁿ subsets including the empty set and the full set — any solution is
O(2ⁿ); you can't beat the output size.
Use this pattern when
- Asked to enumerate **all** subsets / the power set of distinct elements
- Need every combination of choices where each element is independently in or out
- The result must include the empty set and the full set
- Search space is a binary in/out decision per element
Choose another pattern when
- Only the **count** of subsets is needed → it's just 2ⁿ, no enumeration required
- Input has duplicates and you must dedup → Subsets II (sort + skip same-level repeats)
- Need subsets of a fixed size k only → Combinations (LC 77), prune by length
- n is large (> ~20) → 2ⁿ is intractable; the problem likely wants DP or math, not enumeration
Interview takeaway
Subsets is the purest backtracking template: a binary include/exclude choice per element with no constraint to satisfy. The 'record at every node' twist distinguishes it from constraint problems like Combination Sum. Master it and Subsets II, Combinations, and Permutations are one-line variations.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical Backtracking with a Start Index, recording at every node (choose → explore → un-choose). Recognise it whenever you must enumerate the full power set with no constraint. The 'record everywhere' twist (vs only at qualifying leaves) is what distinguishes it from Combination Sum; the same skeleton drives Subsets II, Combinations, and (with used[] instead of start) Permutations.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Subsets IIComing soonInput has duplicates → sort first, then skip `nums[i] == nums[i-1]` when `i > start` to avoid duplicate subsets at the same level.
- CombinationsComing soonOnly subsets of fixed size k → same start-index template but record when `path.size() == k` and prune branches too short to reach k.
- PermutationsOrder matters and all n elements are used → drop the start index, track a used[] set, loop from 0 every level.
- Combination SumAdd a target constraint and allow reuse → recurse with `i` (not `i+1`) and record only when remaining hits 0.