Pattern #21

Backtracking

Important interview questions, thinking patterns, choice trees, pruning, slice mutation traps in Go, and rules for solving backtracking problems.

Must Solve

16 core questions — solve these first.

1.Subsets
Binary choice: Take or Skip at indexmedium
2.Subsets II
Sort array + skip duplicate adjacent choicesmedium
3.Permutations
Unused elements choice + visited boolean arraymedium
4.Permutations II
Sort array + skip duplicate choices at same depthmedium
5.Combination Sum
Reusable element choice (recurse with same index)medium
6.Combination Sum II
Sort + single-use element with duplicate skipmedium
7.Generate Parentheses
Track open & close bracket countsmedium
8.Letter Combinations of a Phone Number
Digit mapping backtracking choicemedium
9.Word Search
Grid DFS 4-directional search + visited restoremedium
10.Palindrome Partitioning
Sub-string palindrome check + partition backtrackmedium
11.N-Queens
Row-by-row queen placement + diagonal conflict pruninghard
12.N-Queens II
Count total valid board configurationshard
13.Sudoku Solver
9x9 grid 1-9 digit trial + row/col/box validationhard
14.Restore IP Addresses
Valid 0-255 segment partitioning recursionmedium
15.Combination Sum III
K numbers summing to N using 1-9 without duplicatesmedium
16.Word Search II
Trie Data Structure + Grid Backtracking DFShard

Also Important

9 more questions worth practicing.

17.Combinations
N choose K start index recursionmedium
18.Beautiful Arrangement
Divisibility check backtracking pruningmedium
19.Matchsticks to Square
4-side sum partitioning + sort descendingmedium
20.Partition to K Equal Sum Subsets
K subset sum buckets + pruningmedium
21.Letter Tile Possibilities
Character count frequency map backtrackingmedium
22.Split a String Into the Max Number of Unique Substrings
HashSet seen substrings backtrackingmedium
23.Maximum Length of a Concatenated String with Unique Characters
Bitmask char set unique concatenationmedium
24.Rat in a Maze
4-directional grid maze path searchmedium
25.Graph Coloring Problem
K-color assignment + vertex neighbor checkmedium

How to Think

Need all possible answers?Backtracking
Need try different choices?Choose, Explore, Undo
Need permutations / subsets / combinations?Backtracking
Need place things with rules (N-Queens, Sudoku)?Backtracking
Need search a path in grid?DFS + Backtracking
Need stop bad paths early?Pruning

Go Backtracking Template (with Slice Copy Protection)

Universal Backtracking Template in Go

func backtrack(path []int, choices []int) {
    if isComplete(path) {
        // IMPORTANT: Make an explicit slice copy in Go!
        copyPath := append([]int(nil), path...)
        results = append(results, copyPath)
        return
    }

    for _, choice := range choices {
        if isValid(choice) {
            // 1. Choose
            path = append(path, choice)

            // 2. Explore
            backtrack(path, choices)

            // 3. Undo
            path = path[:len(path)-1]
        }
    }
}

👉 Always copy slices before appending to results to avoid mutation bugs!

Core Backtracking Pattern & Pruning

1. Choose

Make decision: Add item/digit/board position to current path state.

2. Explore

Recurse to next step or next index in decision tree.

3. Undo (Backtrack)

Pop item from path state so next branch evaluates clean state!

Subsets vs Permutations vs Combinations

Subsets

Decision at each element:
Take or Skip
Generates 2^N subsets

Permutations

Order matters!
Choose unused elements
Generates N! permutations

Combinations

Order does NOT matter!
Use start index to avoid
duplicates like [1,2] & [2,1]

Visual Memory Rule

CHOOSE  →  EXPLORE  →  UNDO
Duplicates  →  Sort array first + skip same-level choices (i > start && nums[i] == nums[i-1])
Pruning     →  Stop early when sum > target or board rule fails

💡 Golden Rule: "Make one choice, explore it fully, undo it, then try the next choice."

Common Interview Mistakes

1. Forgetting to Undo State

Adding to path but forgetting path = path[:len(path)-1] leaks state into parallel branches.

2. Saving Same Slice in Go

Appending path directly to results in Go without copy causes all saved answers to mutate!

3. No Pruning Guard

Exploring impossible paths (e.g. sum > target) causes TLE (Time Limit Exceeded) on $O(2^N)$ search spaces.

4. Duplicate Answer Combinations

For inputs with duplicate elements, sort first and skip same-level duplicates (if i > start && nums[i] == nums[i-1] continue).

Interview Rules

1. Need all possibilities? → Backtracking
2. Subsets? → Take / Skip binary decisions
3. Permutations? → Choose unused elements (visited set)
4. Combinations? → Start index avoids order duplicates
5. Board placement (N-Queens, Sudoku)? → Backtracking
6. Grid word search? → DFS + Backtracking
7. Duplicate inputs? → Sort first + skip same-level duplicates
8. Overall Complexity → O(2^N) or O(N!) time complexity

Small Rules

Rule 1: Backtracking = Recursion + State Undo.
Rule 2: You MUST undo state modifications after returning from recursive call.
Rule 3: Prune invalid branches early to avoid TLE.
Rule 4: Make explicit slice copies before appending path to results in Go.
Rule 5: Always track current path, index, used items, and board state explicitly.

Production Thinking

Cloud Infra Configuration Search → Search region/instance/storage combinations satisfying budget constraints

Employee Shift Scheduling → Assign workers to shifts, backtrack on overlap conflict

Room & Resource Allocation → Assign meeting rooms and resources with pruning for capacity limits

State Space Pruning → Prune invalid branch states early in search engines and constraint solvers

Remember This

Choose              → make decision
Explore             → recurse
Invalid?            → stop
Complete?           → save answer (copy slice!)
Undo                → restore state
Then                → next choice

💡 Golden Rule: "Make one choice, explore it fully, undo it, then try the next choice."