DSA & Implementation · advanced
Backtracking
DFS with state restoration, pruning.
Mental model
Backtracking is "try a choice, recurse, undo if it does not work, try the next one." It explores all possibilities, but you cut whole branches by stopping early when you can prove they will never reach a valid answer.
How to study Backtracking
Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use Backtracking (Wikipedia) to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare Backtracking with the neighboring concepts in its roadmap. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Generate all subsets, Word Search, Permutations and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.
Proof of understanding
- Explain the mechanism from first principles and identify the state it reads or changes.
- Give one situation where the concept is the right choice and one where it is not.
- Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
- Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.
Learn from primary sources
- Backtracking (Wikipedia) (doc)
Practice and explain it back
Generate all subsets
Return all subsets of [1,2]. Use backtracking with include/exclude choice per index.
Expected evidence: [[],[1],[2],[1,2]] (order may vary).
Open the interactive drill →Word Search
LeetCode #79 — Word Search. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/word-search/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Permutations
LeetCode #46 — Permutations. Solve on LeetCode, then implement here if you want it in your drill queue. https://leetcode.com/problems/permutations/
Expected evidence: Pass all LeetCode test cases for this problem.
Open the interactive drill →Review prompts
- What exactly has to be undone after a recursive call returns, and what breaks if you forget?
Build evidence
Use a roadmap capstone to turn this concept into working evidence.
Prerequisites
Related concepts
None assigned yet.