Recursion & Backtracking

Backtracking is a systematic algorithm for generating all solutions to a problem by building candidates incrementally and abandoning (backtracking) candidates that fail constraints. The mental model: you are exploring a decision tree — at each node, you choose one option, recurse into the subtree, then undo the choice and try the next option. The template is always: choose → explore → un-choose. The key insight: backtracking is exhaustive DFS with pruning. Pruning is what makes backtracking practical. Understanding Stacks A stack is a LIFO (Last In, First Out) data structure. Think of a stack of plates — you can only add or remove from the top. Stacks are used for tracking state, backtracking, and expression evaluation. Why stacks are interview favorites: They model function call stacks (recursion) They solve parentheses matching, expression evaluation Monotonic stacks solve "next greater/smaller" problems efficiently Key patterns: Matching pairs: parentheses, brackets, HTML tags Monotonic stack: maintain increasing/decreasing order to find next greater/smaller element in O(n) Expression evaluation: convert infix to postfix, evaluate postfix Backtracking: undo operations (browser history, undo/redo) When to use a stack: "Find the nearest/next greater/smaller element" → Monotonic stack "Check if balanced/valid" → Regular stack "Evaluate expression" → Two stacks (operators operands) Recursion & Backtracking Backtracking systematically explores all possibilities by making choices, exploring, and undoing (backtracking) when a path doesn't work. The Template Subsets Permutations N-Queens Key Problems #78 Subsets, #46 Permutations, #39 Combination Sum #51 N-Queens, #79 Word Search, #37 Sudoku Solver Interview Tip "Backtracking is DFS with pruning. The key is knowing WHEN to prune — every valid pruning condition dramatically reduces the search space." Java Implementation: