Intermediate · Module 12 · Lesson 3
Subsets & combinations
Branch on choices while controlling duplicates.
Lesson 66 of 123
1d streakBacktracking: Exploring State Spaces & Pruning Decisions
Backtracking explores candidates recursively to build combinations. The pattern follows: Choose candidate -> Recurse deeper -> Un-choose candidate (backtrack). This explores the 2^n power set space while maintaining a single reusable buffer.
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(0, nums, new ArrayList<>(), result);
return result;
}
private void backtrack(int start, int[] nums, List<Integer> current, List<List<Integer>> result) {
result.add(new ArrayList<>(current)); // Snapshot valid subset
for (int i = start; i < nums.length; i++) {
current.add(nums[i]); // Choose
backtrack(i + 1, nums, current, result); // Recurse
current.remove(current.size() - 1); // Backtrack (Un-choose)
}
}Active Recall Checkpoint
Why must new ArrayList<>(current) be instantiated when adding to result?
Show answer & explanation
current is a shared mutable buffer. If added directly, result stores references to the same list that eventually mutates back to empty upon complete backtracking.
Use it when
Use backtracking for generating power sets, combinations, permutations, N-Queens, Sudoku solving, and word search grids.
Reconsider when
Reconsider when only count or optimal value is requested (e.g. number of subsets summing to target); dynamic programming is exponentially faster (O(n * target) vs O(2^n)).
Cost Model
Complexity & Trade-offs
When to use it
- Self-similar subproblems, enumeration, constraint solving, and decision trees.
- Generating combinations and permutations.
- Converting overlapping recursion into dynamic programming.
Common mistakes
- Missing a base case or failing to make strict progress.
- Forgetting to undo shared mutable state.
- Using exponential search when states repeat and should be memoized.
Practice prompts
- Reproduce the worked Subsets & combinations example without looking at the trace.
- Change one input condition and explain whether the Subsets & combinations invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check