Backtracking Basics

Backtracking is a problem-solving technique that systematically explores all possible solutions by building candidates step by step and abandoning paths that cannot lead to a valid solution.

It is essentially recursion with choice and undo, making it ideal for problems involving combinations, permutations, and constrained searches.

Core Idea of Backtracking

Backtracking follows a simple pattern:

Choose → Explore → Undo

At each step:

1. Choose an option
2. Explore recursively
3. Undo the choice if it leads to failure

This allows the algorithm to search the entire solution space efficiently.

When Backtracking Is Used

Backtracking is useful when:

• Multiple choices exist at each step
• Only some choices lead to valid solutions
• All solutions or the best solution must be found
• The solution space is exponential

Typical problems include:

• Permutations
• Combinations
• Subset generation
• Sudoku
• N-Queens
• Maze solving

Backtracking Template

Most backtracking problems follow this structure:

backtrack(state):
    if state is complete:
        record solution
        return

    for each choice in choices:
        apply choice
        backtrack(updated state)
        undo choice

This template is reusable across many problems.

Example: Generate All Subsets

Problem

Given a list of numbers, generate all possible subsets.

Input:

[1, 2]

Output:

[]
[1]
[2]
[1, 2]

Rust Implementation

pub fn subsets(nums: &[i32]) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    let mut current = Vec::new();

    backtrack(0, nums, &mut current, &mut result);
    result
}

fn backtrack(
    index: usize,
    nums: &[i32],
    current: &mut Vec<i32>,
    result: &mut Vec<Vec<i32>>,
) {
    result.push(current.clone());

    for i in index..nums.len() {
        current.push(nums[i]);
        backtrack(i + 1, nums, current, result);
        current.pop(); // undo
    }
}

How Backtracking Works (Step-by-Step)

For [1, 2]:

[]
 ├─ [1]
 │   └─ [1, 2]
 └─ [2]

Each branch represents a choice. After exploring a branch, the algorithm backtracks.

Time and Space Complexity

Time Complexity

Backtracking explores all possibilities.

Space Complexity

Backtracking vs Brute Force

Backtracking avoids exploring paths that cannot lead to valid solutions.

Common Backtracking Mistakes

• Forgetting to undo choices
• Modifying shared state incorrectly
• Missing base cases
• Exponential blowup without pruning

Summary

• Backtracking explores solution spaces systematically
• Built on recursion
• Uses choose → explore → undo pattern
• Essential for combinatorial problems