Subsets (BFS-style generation)
Iteratively or recursively build all subsets/permutations/combinations by extending prior results.
Power set, permutations, combinations, letter case permutations, generating parentheses.
There are 2^n subsets, and copying each subset of average size n/2 into the result costs O(n) per subset. The output itself dominates space.
Subset generation has two equivalent framings: BFS-style (start with [[]], for each new element clone every existing subset and append the element) and DFS-style (at each index, choose to include or exclude). Both produce all 2^n subsets in O(n * 2^n) total time — the n factor is the cost of copying each subset.
Permutations extend the same skeleton but the choice at each step is 'which remaining element to place next', giving n! outputs. Combinations restrict to fixed-size subsets, pruning branches that can't possibly reach size k. The key insight is that all three are tree traversals; the shape of the tree is what differs.
For problems with duplicate inputs (subsets-II, permutations-II), sorting first and then skipping duplicates at the same recursion depth avoids generating identical outputs. The skip rule — 'skip if same as previous AND previous wasn't used' — is subtle and a frequent interview stumbling block.
All combinatorial generation is tree traversal: subsets, permutations, and combinations differ only in the choice rule at each node, but share the same O(branching^depth) cost and the same backtracking skeleton.
- Appending a reference to the current path instead of a copy, so all 'results' end up empty after the recursion unwinds.
- For permutations with duplicates, skipping with the wrong condition — the canonical rule is 'if i > 0 && nums[i] == nums[i-1] && !used[i-1], skip'.
- For subsets with duplicates, forgetting to sort the input first, making duplicate detection impossible.
- Generating 2^n outputs when the problem actually wants count or existence, missing an opportunity for DP.
- Off-by-one in combination problems: starting the next recursion at i instead of i+1 (allowing reuse) or vice versa.
- Subsets: include/exclude DFS, or iterative cloning.
- Permutations: swap-in-place or used[]-array DFS.
- Combinations: fixed-size subsets with start-index advancement.
- Combination sum (with reuse): same skeleton but recurse with i instead of i+1.
List<List<Integer>> result = new ArrayList<>();
result.add(new ArrayList<>());
for (int num : nums) {
int n = result.size();
for (int i = 0; i < n; i++) {
List<Integer> subset = new ArrayList<>(result.get(i));
subset.add(num);
result.add(subset);
}
}
return result;Problems using this pattern
3Easiest first · Blind 75 above NeetCode 150