Backtracking Algorithms: When and How to Use Them

Backtracking is a powerful technique for solving constraint satisfaction problems by exploring all possibilities.

The Backtracking Pattern

1. Make a choice

2. Recursively solve with that choice

3. Undo the choice (backtrack)

4. Try next option

Permutations

Generate all permutations of an array:

def permute(nums):
    result = []
    
    def backtrack(current):
        if len(current) == len(nums):
            result.append(current[:])
            return
        
        for num in nums:
            if num not in current:
                current.append(num)
                backtrack(current)
                current.pop()  # Backtrack
    
    backtrack([])
    return result

Combinations

Generate combinations of k elements:

def combine(n, k):
    result = []
    
    def backtrack(start, current):
        if len(current) == k:
            result.append(current[:])
            return
        
        for i in range(start, n + 1):
            current.append(i)
            backtrack(i + 1, current)
            current.pop()  # Backtrack
    
    backtrack(1, [])
    return result

N-Queens Problem

Place n queens on n×n board without attacking:

def solve_n_queens(n):
    result = []
    board = [['.'] * n for _ in range(n)]
    
    def is_safe(row, col):
        # Check column
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        
        # Check diagonals
        for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
            if board[i][j] == 'Q':
                return False
        
        for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
            if board[i][j] == 'Q':
                return False
        
        return True
    
    def backtrack(row):
        if row == n:
            result.append([''.join(row) for row in board])
            return
        
        for col in range(n):
            if is_safe(row, col):
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'  # Backtrack
    
    backtrack(0)
    return result

When to Use Backtracking

- Constraint satisfaction problems

- Need to explore all possibilities

- Problems with "undo" operations

- Permutations, combinations, subsets

Key Tips

1. **Pruning:** Skip invalid paths early

2. **State Management:** Track current state

3. **Base Case:** Define when to stop

4. **Cleanup:** Always undo changes

Backtracking is essential for many interview problems!