Backtracking · LC #78
Subsets
Generate all 2^n subsets via backtracking: at each node immediately add the current subset to results, then explore each remaining element as a branch.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given an integer array `nums` of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets.
Sample I/O
Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] Input: nums = [0] Output: [[],[0]]
Intuition
How to Think About It
Intuition
At every node of the recursion tree, the current path represents a valid subset (including the empty set at the root). By recording the snapshot at each node - not just the leaves - we collect all 2^n subsets.
Core Concept
backtrack(start, curr): add curr[:] to results immediately. For i from start to n-1: push nums[i], recurse with i+1, pop. The start index prevents re-using earlier elements and avoids duplicate subsets.
When to use
Enumerate all subsets of a set; foundation for combination, permutation, and partition problems; whenever you need the power set.
When NOT to use
When n > ~20 (2^n subsets becomes infeasible); when you only need the count (2^n by formula); when duplicates exist in nums (use Subsets II with deduplication).
Key Insights
What to Know Cold
- Record result at every recursive call, not just at leaf nodes.
- Using start index (not a visited array) is the canonical approach for subsets/combinations.
- start=i+1 prevents reuse and ensures lexicographic uniqueness.
- 2^n subsets total; copying each takes O(n) → O(n * 2^n) total time.
- Bit-manipulation alternative: iterate 0..(2^n - 1), bit i = include nums[i].
1 example
Worked Examples
Power set of [1,2,3]
Generate all 8 subsets of [1,2,3].
Backtracking with start index; record at every node.
Output: [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
Template for all backtracking problems - interviewers frequently ask for this as a warm-up before harder variants.