Systematic trial and error. Build solutions incrementally and abandon candidates that fail constraints.
Time
Usually exponential O(2^n) or O(n!)
Space
O(n) recursion depth
Problems
4 must-do
| # | Problem | Difficulty | Asked At |
|---|---|---|---|
| 1 | Subsets | Medium | Google Amazon Meta |
| 2 | Permutations | Medium | Google Microsoft Amazon |
| 3 | Combination Sum | Medium | Amazon Google Airbnb |
| 4 | N-Queens | Hard | Google Amazon Microsoft |
Template: choose → explore → un-choose (backtrack)
Use a visited array or set to avoid duplicates
Pruning: skip invalid states early to reduce time
Subsets = combinations without fixed size
