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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to LeetCode Patterns — University-Style Teaching Notes