Pattern Recognition Drill
Medium Recursion
The Problem
Generate all subsets (power set) of a list of numbers.
What approach would you use?
Think about it before scrolling down.
For each element, branch: include it or exclude it. Collect results at leaf nodes. O(2^n).
Iterate from 0 to 2^n-1. Each bitmask represents a subset. Same O(2^n).
Common Trap
Both approaches are O(2^n) — that's unavoidable since there are 2^n subsets.