Subsets

1. Problem & Core Objective

Given an array of unique integers, return all possible subsets (the power set). No duplicate subsets, any order.

nums = [1,2,3]
→ [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]      8 subsets

Constraints: 1 <= nums.length <= 10 · -10 <= nums[i] <= 10 · all elements unique

What's actually being tested: the backtracking skeleton itself. Subsets is the cleanest possible statement of choose → explore → un-choose, with no pruning and no constraints to satisfy. Every other question in this section is this plus something.

2. First-Principles Thought Process

Count the answers first

Each element is independently in or out. With n elements that's 2^n subsets — 8 for three elements, 1024 for ten.

So the output alone is O(2^n) and no algorithm can beat that. The question isn't "can we be faster than exponential" — it's "can we generate each subset exactly once, without a final deduplication pass".

The decision tree

Two branches per element, n levels, 2^n leaves.

The three lines

path.add(nums[i]);      // CHOOSE
backtrack(i + 1, path); // EXPLORE
path.remove(last);      // UN-CHOOSE

path is a single shared list mutated as the search descends. The un-choose is what makes this backtracking rather than plain recursion — without it, a sibling branch inherits the previous branch's choices and every subsequent answer is wrong.

Why a start index instead of explicit include/exclude

The tree above shows two branches per element. The usual code writes it differently:

for (int i = start; i < nums.length; i++) { ... backtrack(i + 1, path); }

The loop is the "which element do I add next" choice, and i + 1 means each element is used at most once. Same 2^n subsets, fewer explicit branches.

The start parameter also prevents duplicates structurally. Without it the loop would revisit earlier indices and generate [1,2] and [2,1] as different paths — the same subset twice. Starting at start forces indices to increase, so each subset is reachable by exactly one path.

Where to record

Every node is a valid subset, not just the leaves — [1] is a subset on the way to [1,2]. So result.add(new ArrayList<>(path)) goes at the top of the function, before the loop.

That copy matters: path keeps mutating, so storing the reference would leave every entry pointing at the same (eventually empty) list.

3. Solution Paths

Approach 1 — Iterative doubling (no recursion)

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    result.add(new ArrayList<>());                 // start with the empty subset

    for (int n : nums) {
        int size = result.size();                   // snapshot before growing
        for (int i = 0; i < size; i++) {
            List<Integer> copy = new ArrayList<>(result.get(i));
            copy.add(n);
            result.add(copy);
        }
    }
    return result;
}

Each new element doubles the answer set: every existing subset, with and without it.

• Time O(n · 2^n) · Space O(n · 2^n) output

Counter-questions on this approach

⭐ "Why the int size = result.size() snapshot?"

Because the inner loop appends to the same list it's iterating. Without the snapshot, result.size() grows as I add, and the loop would keep extending subsets it just created — producing [1,1], then [1,1,1], and never terminating.

It's the same discipline as the level snapshot in BFS by level: capture the boundary before mutating past it.

⭐ "This is shorter than the recursion. Why teach the recursive one?"

Because this one doesn't generalise. It works for Subsets precisely because there are no constraints — every extension is valid. The moment you need pruning (Combination Sum), a validity check (N-Queens), or a per-level skip (Subsets II), the doubling trick has nowhere to put it.

The recursive skeleton is the one that carries through all nine questions, so it's worth writing here where it's easiest.

"Is it actually faster?"

Marginally — no call stack, better locality. Both are O(n · 2^n) dominated by copying subsets into the output. At n = 10 it's 1024 subsets and neither is measurable.

Approach 2 — Backtracking with a start index (the template)

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), result);
    return result;
}

private void backtrack(int[] nums, int start, List<Integer> path,
                       List<List<Integer>> result) {
    result.add(new ArrayList<>(path));              // every node is a subset — COPY it

    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);                          // choose
        backtrack(nums, i + 1, path, result);       // explore — i+1: no reuse
        path.remove(path.size() - 1);               // un-choose
    }
}

Trace — nums = [1,2,3], showing the order subsets are recorded:

8 subsets ✓

• Time O(n · 2^n) · Space O(n) recursion depth, plus the output

Counter-questions on this approach

⭐ "Why new ArrayList<>(path) instead of just path?"

Because path is a single mutable list reused across the entire search. Adding the reference would put the same object into the result 2^n times — and since the search ends with path empty, every entry would read as [].

The copy is O(n), which is where the n in O(n · 2^n) comes from. It's unavoidable: the output genuinely contains n · 2^n / 2 integers.

⭐ "Why does the recursive call pass i + 1 rather than start + 1?"

Because the loop has already advanced past elements between start and i — those were the "skip" branches. Passing i + 1 means "continue after the element I just chose".

start + 1 would let the loop revisit elements it already skipped at this level, generating [1,3] and then [3,1] — the same subset twice. This is the single most common bug in the template.

⭐ "Why is the result recorded before the loop rather than at a base case?"

Because every prefix is itself a valid subset. [1] is an answer, not just a waypoint to [1,2].

Other problems in this section record only at leaves — Combination Sum records when the target hits zero, N-Queens when all rows are filled. Where you record is the problem-specific part; the skeleton around it doesn't change.

"There's no explicit base case. Doesn't it need one?"

The loop handles it. When start == nums.length the loop body never runs, so the call records its path and returns. An explicit if (start == nums.length) return; would be equivalent and slightly clearer, but it's genuinely unnecessary.

"What happens if you forget the path.remove?"

Every answer after the first deep branch is wrong. path would keep growing — after reaching [1,2,3] it would still hold all three when the loop backs up to try [1,3], producing [1,2,3,3]. It fails loudly on this problem, which is fortunate; in problems with pruning it can fail quietly.

"Why does the order of results not matter here?"

The problem says any order. That's what permits the start-index formulation, which produces them in a specific DFS order rather than by size or lexicographically.

Approach 3 — Bitmask enumeration

public List<List<Integer>> subsets(int[] nums) {
    int n = nums.length;
    List<List<Integer>> result = new ArrayList<>();

    for (int mask = 0; mask < (1 << n); mask++) {       // 0 .. 2^n - 1
        List<Integer> subset = new ArrayList<>();
        for (int i = 0; i < n; i++)
            if ((mask & (1 << i)) != 0) subset.add(nums[i]);
        result.add(subset);
    }
    return result;
}

Each integer from 0 to 2^n − 1 is a subset: bit i set means element i is included.

• Time O(n · 2^n) · Space O(1) extra

Counter-questions on this approach

⭐ "This is the most direct statement of 2^n. Why isn't it the answer?"

It's elegant and I'd mention it — the bijection between integers and subsets is exactly the include/exclude tree, flattened.

Two limits. It caps at n = 31 for int (63 for long), which is fine here but not general. And like the doubling approach, it has nowhere to put pruning — the mask enumerates blindly, so a constraint can only be checked after building each subset, not used to skip whole branches.

"Why 1 << n and not Math.pow(2, n)?"

pow returns a double and needs a cast, introducing precision concerns for no reason. 1 << n is exact integer arithmetic — and at n = 10 gives exactly 1024.

"Does bit order affect the output?"

It changes which subset each mask maps to, but not the set of subsets produced. Iterating bits low-to-high gives elements in array order within each subset, which is usually what you want.

Comparison

4. Why the Optimal Wins

All three are O(n · 2^n), which is optimal — the output itself is that large. So this isn't a complexity comparison at all.

The backtracking version wins because it's the only one that generalises. Subsets has no constraints, so every approach works; the next eight questions add constraints, and only the recursive skeleton has a place to put them:

The framing worth keeping:

Choose, explore, un-choose. The skeleton never changes — only the choices, the base case, and the pruning.

5. Java Prerequisites

The template

private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
    result.add(new ArrayList<>(path));         // record (position varies by problem)
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, i + 1, path, result);
        path.remove(path.size() - 1);
    }
}

Defensive copy on record — new ArrayList<>(path). Storing path itself stores a reference to a list that keeps changing.

path.remove(int) vs remove(Object) — with List<Integer>, remove(0) removes index 0, while remove(Integer.valueOf(0)) removes the value 0. A genuine trap. Use path.remove(path.size() - 1) to pop.

Bit operations — 1 << n is 2^n; (mask & (1 << i)) != 0 tests bit i. See 22.

6. Interview Communication Guide

Clarifying questions: Are elements unique (yes — Subsets II is the duplicate variant)? Does the output order matter (no)? Does order within a subset matter (no — these are sets)? Should the empty subset be included (yes)?

The pitch

"First, the size: each element is independently in or out, so there are 2^n subsets. The output alone is exponential, so no algorithm beats that — the question is generating each subset exactly once without a deduplication pass at the end.

I'd use the backtracking template. Maintain one path list, and at each level loop over the remaining elements: add one, recurse, then remove it. That removal is what makes it backtracking — path is shared across the whole search, so without it a sibling branch inherits the previous branch's choices.

The recursive call passes i + 1, which does two things: each element is used at most once, and indices only increase — so [1,2] and [2,1] can't both be generated. That's structural deduplication rather than filtering afterwards.

I record at the top of the function, before the loop, because every prefix is itself a valid subset — [1] is an answer, not just a waypoint. And I record a copy, since path keeps mutating; storing the reference would leave every entry pointing at the same eventually-empty list.

O(n · 2^n) time, dominated by copying subsets into the output, and O(n) stack.

There are two non-recursive alternatives — iterative doubling, and treating each integer from 0 to 2^n − 1 as a bitmask. Both are neat and both are fine here. But neither has anywhere to put pruning, which is what the rest of this section needs, so the recursive skeleton is the one worth establishing."

Edge cases to volunteer:

Name the single-element case. It's the cheapest check that the empty subset is recorded, which happens only because the result is written before the loop rather than at a leaf.

7. Follow-Up Questions — Modified Constraints

⭐ "What if the input contained duplicates?"

Subsets II, question 4. Sort first so equal values are adjacent, then skip a value that repeats at the same level: if (i > start && nums[i] == nums[i-1]) continue;. The i > start matters — i > 0 would also skip legitimate repeats deeper in the path, and [1,2,2] itself would never be generated. I verified that: the wrong guard produces 4 subsets instead of 6 on [1,2,2].

⭐ "Return only subsets of size k."

Record only when path.size() == k, and prune: if path.size() + (n - i) < k, no completion can reach size k, so stop the loop. That's Combinations (LC 77), and the pruning is what stops it degenerating to full enumeration.

"Return subsets summing to a target."

Record when the running sum matches. If all values were positive you could also prune when the sum exceeds the target — with negatives present, you can't, because a later negative could bring it back. Worth stating, because it's exactly the assumption Combination Sum relies on.

"What if n were 30?"

2^30 is about a billion subsets — roughly 4 GB just to store them as boxed integers. At that size you cannot materialise the answer, so you'd stream them to a consumer via a callback or an Iterator, generating each on demand. The bitmask formulation is natural for that since masks are independent.

"Generate them in lexicographic order."

Sort the input first; the start-index template then produces them in a DFS order that's lexicographic by index. If you need them ordered by size instead, group by path.size() or use the Combinations approach for each k in turn.

"Generate the k-th subset directly, without enumerating the rest."

Use the bitmask bijection: the binary representation of k is the subset. O(n) with no search at all. A nice demonstration that the enumeration order is a numbering, not just a traversal.