Backtracking

Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally and abandoning solutions that fail to satisfy constraints.

When to Use

Problems asking for all possible solutions
Constraint satisfaction problems
Combinatorial problems (permutations, combinations)
Puzzle solving (Sudoku, N-Queens)

Common Patterns

Decision Space

Make decisions at each step, backtrack if invalid

Example: Generate parentheses, letter combinations

Permutations

Generate all orderings of elements

Example: Permutations, permutations II

Subsets/Combinations

Choose subset of elements

Example: Subsets, combination sum

Code Templates

Python

# General backtracking template
def backtrack(result, current, choices, constraints):
    # Base case: solution is complete
    if is_solution(current):
        result.append(current.copy())
        return
    
    # Try each choice
    for choice in choices:
        # Make choice
        if is_valid(choice, current, constraints):
            current.append(choice)
            
            # Recurse
            backtrack(result, current, choices, constraints)
            
            # Undo choice (backtrack)
            current.pop()

# Permutations template
def permute(nums):
    result = []
    
    def backtrack(current, remaining):
        if not remaining:
            result.append(current[:])
            return
        
        for i in range(len(remaining)):
            current.append(remaining[i])
            backtrack(current, remaining[:i] + remaining[i+1:])
            current.pop()
    
    backtrack([], nums)
    return result

# Subsets template
def subsets(nums):
    result = []
    
    def backtrack(start, current):
        result.append(current[:])
        
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    
    backtrack(0, [])
    return result

C++

// General backtracking template
void backtrack(vector<vector<int>>& result, 
               vector<int>& current,
               vector<int>& choices,
               Constraints& constraints) {
    // Base case: solution is complete
    if (isSolution(current)) {
        result.push_back(current);
        return;
    }
    
    // Try each choice
    for (int choice : choices) {
        // Make choice
        if (isValid(choice, current, constraints)) {
            current.push_back(choice);
            
            // Recurse
            backtrack(result, current, choices, constraints);
            
            // Undo choice (backtrack)
            current.pop_back();
        }
    }
}

// Permutations template
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    
    function<void(vector<int>&, vector<int>&)> backtrack = 
        [&](vector<int>& current, vector<int>& remaining) {
        if (remaining.empty()) {
            result.push_back(current);
            return;
        }
        
        for (int i = 0; i < remaining.size(); i++) {
            current.push_back(remaining[i]);
            vector<int> next = remaining;
            next.erase(next.begin() + i);
            backtrack(current, next);
            current.pop_back();
        }
    };
    
    vector<int> empty;
    backtrack(empty, nums);
    return result;
}

// Subsets template
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> current;
    
    function<void(int)> backtrack = [&](int start) {
        result.push_back(current);
        
        for (int i = start; i < nums.size(); i++) {
            current.push_back(nums[i]);
            backtrack(i + 1);
            current.pop_back();
        }
    };
    
    backtrack(0);
    return result;
}