Micro-questions over the backtracking pattern. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The idea
1. Give the Sudoku illustration.
Answer
Fill in a number, check validity, move on. At a dead end, undo the last choice and try a different number.
2. Define backtracking against DFS.
Answer
DFS with one addition: an explicit “undo” step after each recursive call returns, so the same shared state can be reused across branches instead of being copied.
3. What is pruning?
Answer
Cutting off branches that cannot lead to a valid solution — eliminating invalid placements early.
B. The template
4. Write it.
Answer
def backtrack(path, choices):
if is_complete(path):
record(path)
return
for choice in choices:
if not is_valid(choice, path):
continue
path.append(choice) # make the choice
backtrack(path, next_choices(choices, choice))
path.pop() # undo — this is the "backtrack"5. Which line is “the entire idea”?
Answer
path.pop() after the recursive call. Without it, path keeps accumulating across sibling branches that have nothing to do with each other.
6. Why is mutating one shared list better than building a new one per call?
Answer
It is asymptotically cheaper — mutated forward on the way down and unmutated on the way back up, rather than copying at every recursive call.
C. The copy trap
7. Why result.append(path[:]) and not result.append(path)?
Answer
path is the same mutable list object reused across the whole search. Appending a reference means every entry in result points at the same list — which is empty again once backtracking finishes.
8. What general trap is that an instance of?
Answer
Reference-type aliasing — storing a pointer to mutable state instead of a snapshot of it.
9. When is the copy not needed?
Answer
When you record something immutable — a string built with "".join(path), or a tuple — since those cannot be mutated afterwards.
D. Permutations
10. Trace [1,2,3] down the first branch.
Answer
choose 1 → [1]; choose 2 → [1,2]; choose 3 → [1,2,3] complete, record; pop to [1,2], no choices left, pop to [1]; choose 3 → [1,3]; choose 2 → [1,3,2] record; …
11. How does the code stop a value being reused?
Answer
It passes remaining[:i] + remaining[i+1:] — the remaining choices with that one removed.
12. What is the alternative to slicing remaining?
Answer
A used boolean array — avoids the slice per call, at the cost of an extra structure to keep in sync.
E. Complexity
13. What is the typical complexity?
Answer
Exponential — for permutations, for subsets.
14. Is that a sign of a bad implementation?
Answer
No — it is inherent to enumerating every valid arrangement.
15. What is the main practical lever?
Answer
Pruning — checking is_valid early to cut whole invalid branches before recursing.
16. Give the canonical example of pruning paying off.
Answer
N-Queens — reject a queen placement immediately instead of completing the board and checking at the end.
F. Trade-offs
17. What is the recursion risk, and the fix?
Answer
Large inputs hit Python’s recursion limit. Use an iterative approach with an explicit stack.
18. What is the most common bug?
Answer
Forgetting to undo a choice — which silently produces incorrect results rather than an error.
19. State the difference between backtracking and plain DFS.
Answer
DFS traverses a structure that already exists; backtracking explores a space of decisions it generates, undoing each choice before trying the next.
20. Summarise the pattern in one sentence.
Answer
Make a choice, recurse, undo it — and prune as early as you can, because the search space is exponential by nature.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Backtracking — the pattern
- DFS Pattern — Question Bank
- State-Space Search — Question Bank — the genuine-tree case
Software engineering
Infrastructure & security
Computer science
Hardware & engineering