Backtracking

What is Backtracking

Backtracking is a recursive technique for exploring all possible solutions by building a solution incrementally and abandoning ("backtracking") when a partial solution cannot lead to a valid complete solution.

Real-World Analogy

Imagine solving a maze. You walk forward until you hit a dead end. When you hit a dead end, you go back to the last intersection and try a different path. You keep doing this until you find the exit.

That's backtracking — try, if it fails, undo and try something else.

The Pattern

Every backtracking problem follows this template:

void backtrack(state, choices) {
    // Base case: valid solution found
    if (isSolution(state)) {
        result.add(new ArrayList<>(state));  // Must copy!
        return;
    }
    
    // Try each choice
    for (choice : choices) {
        // 1. Choose: add choice to state
        state.add(choice);
        
        // 2. Explore: recurse with updated state
        backtrack(state, remainingChoices);
        
        // 3. Unchoose: remove choice (backtrack)
        state.remove(state.size() - 1);
    }
}

Key Insight: Why Copy the State?

// WRONG: adding reference to state
result.add(state);  // state changes later!

// RIGHT: adding a copy
result.add(new ArrayList<>(state));  // independent copy

When to Use Backtracking

Signal	Example
"Find ALL..."	Find all subsets, all permutations
"Generate all..."	Generate all valid parentheses
"Is there a..."	Is there a valid arrangement?
Constraint satisfaction	N-Queens, Sudoku
Explore and undo	Maze solving, word search

Backtracking vs Other Patterns

Pattern	Structure	Output
Recursion	Linear chain	Single answer
Backtracking	Tree exploration	All valid solutions
DFS	Graph traversal	Visit all nodes
DP	Subproblems	Optimal answer

The Three Steps

Choose: Make a decision (add to current state)
Explore: Recursively explore consequences
Unchoose: Undo the decision (remove from state)

This "choose-explore-unchoose" cycle is the essence of backtracking.

Backtracking Patterns

Pattern 1: Subsets

Generate all possible subsets of a set.

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), result);
    return result;
}

private void backtrack(int[] nums, int start, 
                       List<Integer> state, List<List<Integer>> result) {
    result.add(new ArrayList<>(state));
    
    for (int i = start; i < nums.length; i++) {
        state.add(nums[i]);           // Choose
        backtrack(nums, i + 1, state, result);  // Explore
        state.remove(state.size() - 1);  // Unchoose
    }
}

Time: O(2^n) — each element is either included or not.

Pattern 2: Permutations

Generate all possible orderings.

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, new boolean[nums.length], new ArrayList<>(), result);
    return result;
}

private void backtrack(int[] nums, boolean[] used, 
                       List<Integer> state, List<List<Integer>> result) {
    if (state.size() == nums.length) {
        result.add(new ArrayList<>(state));
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        
        used[i] = true;
        state.add(nums[i]);
        backtrack(nums, used, state, result);
        state.remove(state.size() - 1);
        used[i] = false;
    }
}

Time: O(n! × n) — n! permutations, each takes O(n) to copy.

Pattern 3: Combinations

Choose k items from n items.

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(n, k, 1, new ArrayList<>(), result);
    return result;
}

private void backtrack(int n, int k, int start, 
                       List<Integer> state, List<List<Integer>> result) {
    if (state.size() == k) {
        result.add(new ArrayList<>(state));
        return;
    }
    
    for (int i = start; i <= n; i++) {
        state.add(i);
        backtrack(n, k, i + 1, state, result);
        state.remove(state.size() - 1);
    }
}

Time: O(C(n,k) × k) — C(n,k) combinations.

Pattern 4: Constraint Satisfaction

N-Queens, Sudoku, etc.

// N-Queens template
private void backtrack(int row, int n, 
                       List<Integer> queens, List<List<String>> result) {
    if (row == n) {
        result.add(createBoard(queens, n));
        return;
    }
    
    for (int col = 0; col < n; col++) {
        if (isValid(queens, row, col)) {
            queens.add(col);        // Choose
            backtrack(row + 1, n, queens, result);  // Explore
            queens.remove(queens.size() - 1);  // Unchoose
        }
    }
}

Pattern Selection Guide

Pattern	Key Question	Example
Subsets	Include or exclude each item?	Subsets, Subsets II
Permutations	What order?	Permutations, Permutations II
Combinations	Which k items?	Combination Sum, Combinations
Constraint	Valid arrangement?	N-Queens, Sudoku, Word Search

Pruning the Search Space

Pruning means stopping early when you know a path cannot lead to a valid solution.

Why Prune?

Without pruning, backtracking explores ALL possibilities. With pruning, you skip impossible branches.

Example: Combination Sum

Find all combinations that sum to target.

// WITHOUT pruning (slower)
for (int i = start; i < candidates.length; i++) {
    state.add(candidates[i]);
    backtrack(candidates, target - candidates[i], i, state, result);
    state.remove(state.size() - 1);
}

// WITH pruning (faster)
Arrays.sort(candidates);  // Sort first!
for (int i = start; i < candidates.length; i++) {
    if (candidates[i] > target) break;  // PRUNE: no point continuing
    state.add(candidates[i]);
    backtrack(candidates, target - candidates[i], i, state, result);
    state.remove(state.size() - 1);
}

Pruning Techniques

Sort first: Enables early termination
Bound checking: If current state can't possibly lead to solution, stop
Feasibility check: Before choosing, verify the choice is valid
Symmetry breaking: Avoid exploring equivalent solutions

Example: N-Queens Pruning

private boolean isValid(List<Integer> queens, int row, int col) {
    for (int r = 0; r < row; r++) {
        int c = queens.get(r);
        if (c == col) return false;           // Same column
        if (Math.abs(r - row) == Math.abs(c - col)) return false;  // Diagonal
    }
    return true;
}

Only try columns that are valid — don't even recurse on invalid ones.

Complexity with Pruning

Problem	Without Pruning	With Pruning
N-Queens	O(n^n)	O(n!)
Combination Sum	O(2^n)	Much faster in practice
Sudoku	O(9^81)	O(1) in practice

Pruning doesn't change worst-case complexity, but dramatically improves average-case performance.

Java Implementation Patterns

Complete Template

public class BacktrackingTemplate {
    private List<List<Integer>> result = new ArrayList<>();
    
    public List<List<Integer>> solve(int[] nums) {
        backtrack(nums, 0, new ArrayList<>());
        return result;
    }
    
    private void backtrack(int[] nums, int start, List<Integer> state) {
        // Base case (if needed)
        if (/* valid solution */) {
            result.add(new ArrayList<>(state));  // COPY!
            return;
        }
        
        // Explore choices
        for (int i = start; i < nums.length; i++) {
            // Prune: skip invalid choices
            if (/* invalid */) continue;
            
            // Choose
            state.add(nums[i]);
            
            // Explore
            backtrack(nums, i + 1, state);
            
            // Unchoose
            state.remove(state.size() - 1);
        }
    }
}

Subsets Template

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    subsetsHelper(nums, 0, new ArrayList<>(), result);
    return result;
}

private void subsetsHelper(int[] nums, int start, 
                           List<Integer> current, List<List<Integer>> result) {
    result.add(new ArrayList<>(current));
    
    for (int i = start; i < nums.length; i++) {
        current.add(nums[i]);
        subsetsHelper(nums, i + 1, current, result);
        current.remove(current.size() - 1);
    }
}

Permutations Template

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    permuteHelper(nums, new boolean[nums.length], new ArrayList<>(), result);
    return result;
}

private void permuteHelper(int[] nums, boolean[] used, 
                           List<Integer> current, List<List<Integer>> result) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        
        used[i] = true;
        current.add(nums[i]);
        permuteHelper(nums, used, current, result);
        current.remove(current.size() - 1);
        used[i] = false;
    }
}

Word Search Template

public boolean exist(char[][] board, String word) {
    int m = board.length, n = board[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (dfs(board, word, i, j, 0)) return true;
        }
    }
    return false;
}

private boolean dfs(char[][] board, String word, int r, int c, int index) {
    if (index == word.length()) return true;
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return false;
    if (board[r][c] != word.charAt(index)) return false;
    
    char temp = board[r][c];
    board[r][c] = '#';  // Mark visited
    
    boolean found = dfs(board, word, r+1, c, index+1) ||
                    dfs(board, word, r-1, c, index+1) ||
                    dfs(board, word, r, c+1, index+1) ||
                    dfs(board, word, r, c-1, index+1);
    
    board[r][c] = temp;  // Unmark (backtrack)
    return found;
}

Practice Problems

0 / 5 solved

Hard N-Queens

Backtracking

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Return the number of distinct solutions.

Example:

Input: n = 4

Output: 2

There are two distinct solutions to the 4-queens puzzle.

Edge Cases:

n=1: 1 solution
n=2: 0 solutions (impossible)
n=3: 0 solutions (impossible)

Medium Subsets

Backtracking / Bit Manipulation

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]

Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

All 2^3 = 8 subsets.

Edge Cases:

Single element: [1] → [[],[1]]
Two elements: [1,2] → [[],[1],[1,2],[2]]
Negative numbers: [-1,0,1] → [[],[-1],[-1,0],[-1,0,1],[-1,1],[0],[0,1],[1]]

Medium Permutations

Backtracking - Permutations

Given an array nums of distinct integers, return all possible permutations. You can return the answer in any order.

Example:

Input: nums = [1,2,3]

Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

All 3! = 6 permutations are generated.

Edge Cases:

Single element — one permutation: [[1]]
Two elements — two permutations
All negative numbers
Contains zero
Maximum length (6) — 720 permutations

Medium Combination Sum

Backtracking

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. The same candidate may be chosen an unlimited number of times.

Example:

Input: candidates = [2,3,6,7], target = 7

Output: [[2,2,3],[7]]

2 + 2 + 3 = 7 and 7 = 7.

Edge Cases:

Single candidate equal to target: [1], target=1 → [[1]]
All candidates greater than target: [5,6], target=3 → []
Target equals sum of all candidates: [1,2,3], target=6 → [[1,2,3]]

Medium Word Search

Backtracking on Grid

Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells (horizontally or vertically). The same cell may not be used more than once.

Example:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

Output: true

ABCCED is a valid path.

Edge Cases:

Single cell board: [['A']], word='A' → true
Word longer than board cells: impossible path
Word not in board: return false

Flashcards

Question

What are the 3 steps of backtracking?

Click to reveal answer

Answer

1. Choose: add a choice to the current state. 2. Explore: recursively explore with the updated state. 3. Unchoose: remove the choice to try other options.

Question

When do you use backtracking?

Click to reveal answer

Answer

When the problem asks to find ALL valid solutions, generate all possibilities, or check if any valid arrangement exists.

Question

Why must you copy the state when adding to results?

Click to reveal answer

Answer

The state list is modified during backtracking. If you add a reference instead of a copy, all results will point to the same (final) state.

Revision Notes

Key Takeaways

1. Backtracking explores all possibilities by choosing, exploring, and unchoosing
2. Always copy the state when adding to results (not a reference)
3. Prune impossible branches to improve performance
4. Subsets: O(2^n), Permutations: O(n!), Combinations: O(C(n,k))
5. Identify the pattern: subsets, permutations, combinations, or constraint

Interview Tips

• Clarify: do you need all solutions or just one?
• Start with the template, then customize
• Mention pruning to show optimization awareness
• Trace through a small example first
• State the time complexity using the pattern formula

Cheat Sheet

Backtracking Cheat Sheet

Template:

void backtrack(state, choices) {
    if (isSolution(state)) {
        result.add(copy(state));
        return;
    }
    for (choice : choices) {
        state.add(choice);    // Choose
        backtrack(state, ...); // Explore
        state.remove(choice); // Unchoose
    }
}

Patterns:

Pattern	Key	Example
Subsets	Include/exclude	Subsets, Subsets II
Permutations	Order matters	Permutations, Next Permutation
Combinations	Choose k	Combination Sum, Combinations
Constraint	Valid arrangement	N-Queens, Sudoku

Pruning:

Sort candidates first
Skip if candidate > remaining target
Check validity before recursing

Complexity:

Subsets: O(2^n)
Permutations: O(n! × n)
Combinations: O(C(n,k) × k)
N-Queens: O(n!)

Common Mistakes:

Forgetting to copy state → all results are same
Not unchoosing → wrong results
No pruning → TLE on large inputs

What is Backtracking

Real-World Analogy

The Pattern

Key Insight: Why Copy the State?

When to Use Backtracking

Backtracking vs Other Patterns

The Three Steps

Backtracking Patterns

Pattern 1: Subsets

Pattern 2: Permutations

Pattern 3: Combinations

Pattern 4: Constraint Satisfaction

Pattern Selection Guide

Pruning the Search Space

Why Prune?

Example: Combination Sum

Pruning Techniques

Example: N-Queens Pruning

Complexity with Pruning

Java Implementation Patterns

Complete Template

Subsets Template

Permutations Template

Word Search Template

Practice Problems

Quiz

Flashcards

Revision Notes

Key Takeaways

Interview Tips

Cheat Sheet

Backtracking Cheat Sheet