The purest backtracking template there is: fixed depth, no pruning, no constraints. The output is sorted before printing only so the grader can compare it — LeetCode accepts any order.

Time $O(4^n \cdot n)$ — at most 4 letters per digit, and joining each word costs $O(n)$. Space $O(n)$ for the path, excluding the output.

• Empty input returns [][], not [""][""]. This is the single most-failed test case on the problem. Zero digits spell zero words, not one empty word — and the bare recursion would happily record the empty path.
• path.pop()path.pop() after the recursive call is what makes the shared pathpath list safe. Forgetting it leaks letters into sibling branches.
• 7 and 9 have four letters, 2-6 and 8 have three. Hard-coding three breaks "79""79", which is why it is in the tests.
• Appending path[:]path[:] versus "".join(path)"".join(path) — joining copies anyway, so strings are safe to store. When the answer is a list, you must copy explicitly; that trips people on the next problem.

Follow-ups you should expect: “Iteratively?” — build the answer level by level, or use itertools.product(*[pad[d] for d in digits])itertools.product(*[pad[d] for d in digits]), which is the one-liner worth mentioning after you have shown the manual version. “Return only combinations in a dictionary?” — pass a trie down and prune the moment a prefix is impossible; that is the T9 autocomplete question. “Digits 1 and 0?” — they map to nothing, so the answer is empty. “10 digits?” — $4^{10}$ is a million words, so you would stream them with a generator rather than materialise a list.

Backtracking on a grid. The difference from the flood-fill DFS in the graph section is the undo: flood fill marks a cell visited forever, because it only cares whether a region is reachable. Here a cell that fails on one path must be available to a different path, so the mark has to be temporary.

Time $O(rc \cdot 3^L)$ where $L$ is the word length — after the first step only three directions are worth trying, since the fourth is where you came from. Space $O(L)$ for the recursion.

• The mark-and-restore is the whole problem. Without the mark, "ABCB""ABCB" returns TrueTrue by bouncing between the BB and the CC. Without the restore, the second and later starting cells search a board full of ##.
• Base cases before bounds arithmetic. Checking i == len(word)i == len(word) first means a full match never needs the cell to exist.
• "A""A" returns TrueTrue — a one-character word matches immediately, and the success check must fire before any neighbour is examined.
• "ABCESEEEFS""ABCESEEEFS" returns FalseFalse on this board. It is a real path on the common variant board that has EE at row 1 column 2 — here that cell is a CC, so the path dies. A good reminder to read the grid you were actually given.
• Restoring word[i]word[i], not the original character, is safe only because the cell matched word[i]word[i] to get here. That is a small proof worth having ready.

Follow-ups you should expect: “Search many words at once (LC 212)?” — build a trie of the words and walk the grid once against the trie; running this solution per word is far too slow. “Prune early?” — if the board’s letter counts cannot cover the word, fail immediately; also search from whichever end of the word is rarer on the board. “Diagonals allowed?” — eight directions instead of four. “Reuse allowed?” — drop the marking, and note the search may then not terminate without a depth bound. “Return the path?” — thread a list of coordinates through the recursion.

The classic constraint-satisfaction backtrack, and the reason it is a Hard is the encoding, not the recursion.

Two observations collapse the search space:

1. One queen per row. Any valid board has exactly one queen per row, so a partial solution is a list of columns and the recursion depth is nn — not $n^2$ cells to consider.
2. Diagonals are arithmetic. Every cell on a // diagonal shares r + cr + c; every cell on a \\ diagonal shares r - cr - c. So three sets replace what would otherwise be an $O(n)$ scan per candidate.

Without pruning there are $n!$ column permutations to test; with these three sets the illegal branches die at the moment they are created, which is what makes n = 9n = 9 instant.

Time exponential — bounded by $n!$ but hugely pruned in practice. Space $O(n)$ for the sets and path, plus the output.

• Undo everything you did, and note the code undoes in reverse order. Leaving one set dirty silently loses solutions rather than crashing, which is the worst kind of bug.
• n = 2n = 2 and n = 3n = 3 have no solutions, and the answer is an empty list, not an error. Those two are the reason the counts start [1, 0, 0, 2, ...][1, 0, 0, 2, ...].
• The counts 1, 0, 0, 2, 10, 4, 401, 0, 0, 2, 10, 4, 40 for n = 1..7n = 1..7 are worth recognising — the non-monotonic dip at n = 6n = 6 surprises people and is a good self-check.
• discarddiscard versus removeremove — either works here since the value is definitely present; discarddiscard just will not mask an ordering bug with a KeyErrorKeyError.

Follow-ups you should expect: “Only the count (LC 52)?” — identical search, increment a counter instead of building boards, and you can then use bitmasks: colscols, diagdiag and antianti as integers, with the available squares computed as ~(cols | diag | anti)~(cols | diag | anti). That is the fastest known formulation and a strong signal in an interview. “Find just one solution?” — return as soon as the first is complete. “Symmetry?” — restrict the first row to the left half and mirror the results, roughly halving the work. “Very large nn?” — constructive formulas exist for placing nn non-attacking queens; enumerating all solutions is intractable well before n = 30n = 30.