Recursion & Backtracking Guide

Recursion and Backtracking for Coding Interviews

Recursion underpins tree traversals, graph search, and dynamic programming — three of the most common interview categories. Backtracking, a specialized form of recursion, appears in approximately 10% of coding interviews and is the technique behind problems like N-Queens, Sudoku solver, and permutation generation.

The backtracking template: make a choice, recurse, undo the choice (backtrack). This explore-and-retreat pattern generates all valid solutions while pruning invalid paths early.

The Recursion Framework

1. Base case — When to stop recursing (empty array, leaf node, target reached)
2. Recursive case — Break problem into smaller subproblems
3. Combine — How to combine results from subproblems

Backtracking Template

For problems like subsets, permutations, and combinations:

1. Choose — Pick an element to include
2. Explore — Recurse with the choice made
3. Unchoose — Remove the element (backtrack) before trying the next option

Classic Backtracking Problems

• Generate all subsets (2^n solutions)
• Generate all permutations (n! solutions)
• N-Queens (place N queens on NxN board)
• Word search in 2D grid
• Combination sum (find combinations that sum to target)

Recursion is prerequisite for tree algorithms, graph algorithms, and dynamic programming. Practice with AissenceAI.