Recursion and Backtracking Complete Guide — Patterns, Templates, and Top 30 Problems

Problem Statement#

This is a meta-guide that describes the recursion and backtracking framework used by every problem in this series. Backtracking is systematic depth-first exploration of a decision tree with optional pruning to skip dead ends.

Constraints:

• Each decision must be reversible (push/pop, mark/unmark, swap/swap-back)
• The state must be testable for completeness and validity at each node
• Recursion depth is bounded by the longest path through the decision tree
• Pruning is correctness-preserving: skip only branches that cannot produce a valid solution

Input:  An enumeration problem ("generate all", "find any", "count valid")
Output: All valid solutions, the first valid solution, or the count

Why This Problem Matters#

Recursion and backtracking show up in nearly every senior interview loop. Amazon, Google, Meta, and Microsoft all reach for this family when they want to test how well a candidate can model a problem as a search over a tree of decisions. Subsets, permutations, combinations, N-Queens, Sudoku, word search, expression generation, and palindrome partitioning all share the same skeleton.

Beyond interviews, backtracking is the engine behind constraint solvers, SAT solvers, AI planners, and many production systems that need to enumerate or search a structured space. Understanding the framework once means you can recognize the pattern instantly and write the code without thinking — which is exactly what an interviewer needs to see in 35 minutes.

The single biggest reason candidates struggle is treating each problem as new. Backtracking has only a handful of templates. Once you internalize choose-explore-unchoose and learn how to recognize the cue words, the entire family collapses into variations of one idea.

The Core Insight#

Backtracking is a depth-first walk of an implicit decision tree. At every node you make a choice, recurse into the resulting subtree, then undo the choice so the next sibling branch starts from a clean state. The three lines that matter are always the same: make the choice, explore, undo the choice.

The framework has only four moving parts: a base case that records or returns a solution, a pruning check that aborts hopeless branches early, a loop over candidate choices, and the choose-recurse-unchoose triple inside that loop. Every problem in the series fills in those four slots differently.

Visual Dry Run#

Solution (Optimal)#

class Solution:
    def backtrack_template(self, choices):
        result = []
 
        def bt(state):
            # 1. Base case: state is a complete solution
            if self.is_complete(state):
                result.append(self.snapshot(state))
                return
 
            # 2. Pruning: cut hopeless subtrees early
            if self.should_prune(state):
                return
 
            # 3. Iterate over candidate choices at this node
            for choice in self.candidates(state, choices):
                if not self.is_valid(state, choice):
                    continue
                self.choose(state, choice)   # CHOOSE
                bt(state)                    # EXPLORE
                self.unchoose(state, choice) # UNCHOOSE
 
        bt(self.initial_state())
        return result

var backtrackTemplate = function(choices) {
    const result = [];
 
    const bt = (state) => {
        // 1. Base case: state encodes a complete solution
        if (isComplete(state)) {
            result.push(snapshot(state));
            return;
        }
 
        // 2. Pruning: stop branches that cannot improve the answer
        if (shouldPrune(state)) return;
 
        // 3. Iterate over candidate next moves
        for (const choice of candidates(state, choices)) {
            if (!isValid(state, choice)) continue;
            choose(state, choice);    // CHOOSE
            bt(state);                // EXPLORE
            unchoose(state, choice);  // UNCHOOSE
        }
    };
 
    bt(initialState());
    return result;
};

Time: Depends on the size of the decision tree, typically O(branching_factor ^ depth) before pruning Space: O(depth) for the recursion stack plus O(state_size) for the path

The 7 Core Patterns#

1. Subsets / Power Set — at each index decide include or exclude. Tree depth n, 2^n leaves.
2. Permutations — at each slot pick any unused element. n! leaves with a used array or in-place swap.
3. Combinations — choose k of n with a start index that prevents revisiting earlier elements.
4. Constraint satisfaction — N-Queens and Sudoku style placements with row, column, and diagonal sets.
5. Path finding on a grid — DFS with mark-visited and unmark on the way back, used for word search and maze enumeration.
6. Partitioning — split a string or array into valid groups, with palindrome partitioning and IP restoration as canonical examples.
7. Expression generation — insert operators or parentheses, used in generate parentheses and expression add operators.

Pruning Strategies That Matter#

• Sort the input first when ordering enables early termination (combination sum, candidate skipping)
• Precompute validity tables (palindrome DP, neighbor masks) so each check is O(1)
• Bound by remaining capacity: stop when len(path) + remaining < target_size
• Use seen sets to skip duplicate sibling branches at the same recursion level
• Symmetry-break by fixing the first decision when the problem is rotationally symmetric

Complexity Quick Reference#

Common Mistakes#

• Recording state by reference instead of taking a snapshot, so backtracking mutates already-stored answers
• Forgetting the unchoose step, which leaks state into sibling branches
• Confusing start-index (combinations, subsets) with used-array (permutations)
• Skipping the sort before applying duplicate-skip rules — adjacency is required
• Pruning incorrectly and dropping valid solutions instead of just dead-ends

Interview Tips#

• Say the four-part skeleton out loud before coding: base case, pruning, loop, choose-explore-unchoose
• Draw the decision tree for n=3 on the whiteboard before writing code
• State the time complexity in terms of the tree shape, not just big-O
• Mention pruning strategies even when not implementing them — interviewers note the awareness
• When duplicates are present, sort first and explain the skip condition before writing it

Follow-up Questions#

• When does DP replace backtracking? Hint: when subproblems overlap and you only need a count or boolean answer.
• How do you handle infinite reuse vs single-use of the same element? Hint: pass i vs i+1 to the recursive call.
• How do you generalize to BFS for shortest-path-style enumeration? Hint: queue of states with visited tracking.
• How do you bound memory when the answer set is exponential? Hint: yield generators or stream solutions.
• When can a bitmask replace a boolean used array? Hint: when n is at most 20 to 22.

Key Takeaways#

• Backtracking is depth-first traversal of a decision tree with optional pruning
• The universal skeleton is base case, pruning, loop over choices, choose-explore-unchoose
• Subsets use a start index, permutations use a used array, combinations use both
• Always snapshot the state when recording (slice in Python, spread in JavaScript)
• Sort first when duplicate-skip rules will be applied at sibling level
• Pruning correctness preservation matters more than speed — never prune valid branches
• Recognize the cue: "generate all", "find all valid", "place N", "partition into" all signal backtracking