DSA & Algorithms
Part 21 of 21 · DSA Interview PatternsBacktracking & Search Trees — Subsets, Permutations, Combinations & Pruning
Backtracking templates with choose/explore/unchoose and pruning for interviews.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
You must list candidates, with pruning
Prefer
Choose, explore, unchoose
Subsets, permutations, and combinations share the skeleton. Pruning is what keeps N-Queens and word search interview-sized.
- Subsets pass a start index and grow every length.
- Permutations mark used indexes.
- The path must be copied into the answer list.
Alternative
DP when the question asks for every structure
DP counts or optimizes. It does not list the combinations unless you add reconstruction.
- Forgetting to pop or unmark.
- Appending the live path object and then mutating it.
- No prune, so the search really is b to the d.
Build the path, then undo
The undo is not optional. It is the difference between one path and a corrupted tree.
- 1
Choose a candidate
Start index for subsets. A used flag for permutations. - 2
Explore or prune
Dead ends return before the recursive call. - 3
Undo
Pop the value and clear the mark before the next sibling.
Overview
Backtracking templates with choose/explore/unchoose and pruning for interviews.
Below is the full pattern: when to reach for it, a top-down picture, runnable Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
When to use / recognition cues
Use when you must enumerate candidates (subsets, permutations, combinations) with prune.
Recognition cues
- subsets / permutations / combinations
- N-Queens / sudoku
- palindrome partitioning
- word search on board
Mental model
Decisions
- 1
Step 1 State - path so far and start index
- nextStep 2 Path is a full answer?
- ?
Step 2 Path is a full answer?
- yesStep 3 Record a copy of path
- noStep 4 Pick the next candidate
- 3
Step 3 Record a copy of path
- appended path itself, not a copyFailure path - every saved answer mutates to empty
- 4
Step 4 Pick the next candidate
- nextStep 5 Can this branch still succeed?
- ?
Step 5 Can this branch still succeed?
- noStep 6a Prune - skip it, no recursion
- yesStep 6b Choose - append, then recurse
- 6
Step 6a Prune - skip it, no recursion
- nextStep 4 Pick the next candidate
- 7
Step 6b Choose - append, then recurse
- nextStep 7 Unchoose - pop from path
- 8
Step 7 Unchoose - pop from path
- nextStep 4 Pick the next candidate
- 9
Failure path - every saved answer mutates to empty
Lesson map
Backtracking & Search Trees — Subsets, Permutations, Combinations & Pruning
Backtracking templates with choose/explore/unchoose and pruning for interviews.
Architecture. Step 1 State - path so far and start index Ready. Step 2 Path is a full answer? Ready. Step 3 Record a copy of path Ready. Step 4 Pick the next candidate Ready. Step 5 Can this branch still succeed? Ready. Step 6a Prune - skip it, no recursion Ready. Step 6b Choose - append, then recurse Ready. Step 7 Unchoose - pop from path Ready. Failure path - every saved answer mutates to empty Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB S["Step 1 State - path so far and start index Ready"] G["Step 2 Path is a full answer? Ready"] O["Step 3 Record a copy of path Ready"] C["Step 4 Pick the next candidate Ready"] P["Step 5 Can this branch still succeed? Ready"] X["Step 6a Prune - skip it, no recursion Ready"] D["Step 6b Choose - append, then recurse Ready"] U["Step 7 Unchoose - pop from path Ready"] F["Failure path - every saved answer mutates to empty Ready"] S -->|continues| G G -->|yes| O G -->|no| C C -->|continues| P P -->|no| X P -->|yes| D D -->|continues| U U -->|continues| C X -->|continues| C O -->|appended path itself, not a copy| F
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity analysis
- Subsets O(n * 2^n); permutations O(n * n!); pruning cuts whole subtrees, so it can shrink the explored states a lot, but the worst case is usually unchanged.
- Space O(n) path depth (+ output).
Common pitfalls & interview traps
LeetCode drill (real problems)
- Subsets
- Permutations
- Combinations
- Combination Sum
- N-Queens
- Word Search
- Palindrome Partitioning
- Sudoku Solver
Go deeper
- Back to the pattern map.
- NeetCode roadmap
- CP-Algorithms
Interview Q&A
Template?
Answer
choose → explore → unchoose; push answer at valid leaf/state.
Subsets vs combos?
Answer
Subsets all lengths; combos fixed k.
Duplicates?
Answer
Sort; skip nums[i]==nums[i-1] when i>start / not used.
Combination sum reuse?
Answer
Recurse i not i+1 to reuse same coin.
Pruning example?
Answer
N-Queens attack checks; remaining length bounds.
Word search?
Answer
DFS board with visited mark/unmark.