Backtracking

Explore all candidate solutions incrementally, abandoning ('pruning') a branch as soon as it can't lead to a valid solution.

When to use it

Generate all permutations/combinations/subsets.
Constraint satisfaction: N-Queens, Sudoku solver, word search on a grid.

Signals in the problem statement

'Generate all', 'find all valid arrangements'.

Common pitfalls

Forgetting to un-mark/undo state when backtracking out of a branch (mutating shared state without restoring it).
Missing early pruning, making a technically-correct solution too slow for constraints.

Practice Problems

Word Search

Medium

Asked at: Amazon, Meta, Microsoft

Practiced

Given a 2D board and a word, find if the word exists in the grid (constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring).

Time: O(m*n * 4^L), L=word length · Space: O(L) recursion