Subsets
Why it exists
Problem: We need to generate the power set (all possible combinations) of an array of distinct elements. Trying to generate combinations cleverly often leads to missed subsets or duplicates.
Naive approach: Using multiple nested loops, which is impossible since the number of loops depends on the subset size.
Better idea: Frame the problem as a sequence of independent yes/no decisions. For each element, decide whether to include it or exclude it. This perfectly enumerates the power set without duplicates.
Mental model
At every item on a buffet line, you have exactly two choices: put it on your plate, or walk past it.
We traverse a binary decision tree. At index `i`, we branch left (take `nums[i]`) and branch right (skip `nums[i]`). The recursion depth is `n`, leading to 2^n leaves. Every single node in this tree represents a valid subset.
Repeated decision: At the current element index, do I include this element in my subset, or do I exclude it?
Explanation
Subset generation is fundamentally a binary choice per element: include it, or exclude it.
Imagine the array `[1, 2]`. The state-space tree looks like this:
```text
[]
/ \
(take 1) (skip 1)
/ \
[1] []
/ \ / \
(t2) (s2) (t2) (s2)
/ \ / \
[1,2] [1] [2] []
```
The depth is `n` (the number of elements). At each step, we have 2 branches, resulting in exactly `2^n` leaves. Each leaf (and in fact, every node) is a valid subset.
There are two common idioms to record the subsets:
1. **Record at every node:** Start the recursive function by immediately appending `path.copy()` to the results. Then loop `i` from `start_index` to `n-1`, append `nums[i]`, recurse with `i + 1`, and pop. This is the 'for-loop' idiom.
2. **Record at leaves only:** Pass the current `index`. At index `n`, record `path.copy()`. Otherwise, make two explicit recursive calls: one with `nums[index]` appended to `path`, and one without it.
Both are valid, but the for-loop idiom is extremely common and extends elegantly to other backtracking problems. The time complexity is O(n * 2^n) because there are 2^n subsets, and copying each subset into the result array takes up to O(n) time.
Key points
- Forward-only recursion: By always passing `i + 1` into the next recursive call, we artificially enforce an order, which guarantees we don't produce permutations like `[1, 2]` and `[2, 1]`.
Pattern: Include/Exclude Decision
Recognition cues:
- Generate all combinations
- Power set
Engineering examples
Testing feature flags
Testing software behavior under all possible combinations of boolean feature flags.
Subset generation creates the exhaustive power set of configurations to test.
Query planners
Evaluating different join orders in databases.
A query optimizer might generate subsets of joined tables to estimate execution costs.
Common mistakes
- Appending the path reference: Writing `result.append(path)` instead of `result.append(path.copy())`. You must deep-copy the path before recording it.
Recall questions
- What is the size of the state-space tree for subsets of an array of length n?
- In the include/exclude tree, which nodes represent valid subsets?
- What is the time complexity of generating subsets, and why?
Questions & answers
Generate all subsets of an array with distinct integers.
Use backtracking with a for-loop idiom. Record `path.copy()` at every node. Loop `i` from `start_index` to end, choose `nums[i]`, recurse with `start_index = i + 1`, then un-choose.
Approach: Standard subsets template.
How do you avoid generating duplicate combinations?
By always recursing with `start_index = i + 1` (or `index + 1`). This ensures we only move forward in the array and never look backward, preventing different orderings of the same elements.
Approach: Monotonic index advancement is the invariant that prevents permutation-like duplicates.
Continue learning
Previous: Backtracking template