Backtracking

Backtracking is an algorithmic technique for solving problems by trying to build a solution incrementally and abandoning ("backtracking" from) solutions that fail to satisfy constraints.

What is Backtracking?

Backtracking systematically explores all possible solutions by:

1. Making a choice
2. Exploring consequences
3. Undoing the choice if it leads to invalid solution (backtrack)
4. Trying the next option

Think of it as exploring a maze: try a path, if it's a dead end, go back and try another path.

Generate All Subsets

Generate all possible subsets of a set.

def generate_subsets(nums):
    result = []
    
    def backtrack(start, current):
        # Add current subset
        result.append(current[:])
        
        # Try adding each remaining element
        for i in range(start, len(nums)):
            current.append(nums[i])      # Make choice
            backtrack(i + 1, current)    # Explore
            current.pop()                 # Undo choice (backtrack)
    
    backtrack(0, [])
    return result

Generate All Permutations

Generate all possible arrangements of elements.

def generate_permutations(nums):
    result = []
    
    def backtrack(current):
        # Base case: complete permutation
        if len(current) == len(nums):
            result.append(current[:])
            return
        
        # Try each unused number
        for num in nums:
            if num in current:
                continue  # Already used
            
            current.append(num)        # Make choice
            backtrack(current)         # Explore
            current.pop()              # Backtrack
    
    backtrack([])
    return result

Combination Sum

Find all combinations that sum to a target.

def combination_sum(candidates, target):
    result = []
    
    def backtrack(start, current, remaining):
        # Base case: found valid combination
        if remaining == 0:
            result.append(current[:])
            return
        
        # Base case: exceeded target
        if remaining < 0:
            return
        
        # Try each candidate
        for i in range(start, len(candidates)):
            current.append(candidates[i])
            # Can reuse same element, so pass i not i+1
            backtrack(i, current, remaining - candidates[i])
            current.pop()
    
    backtrack(0, [], target)
    return result

N-Queens Problem

Place N queens on an N×N chessboard so no two queens attack each other.

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 diagonal (top-left)
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        
        # Check diagonal (top-right)
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j += 1
        
        return True
    
    def backtrack(row):
        if row == n:
            result.append([''.join(r) for r in board])
            return
        
        for col in range(n):
            if is_safe(row, col):
                board[row][col] = 'Q'  # Place queen
                backtrack(row + 1)
                board[row][col] = '.'  # Backtrack
    
    backtrack(0)
    return result

Sudoku Solver

def solve_sudoku(board):
    def is_valid(row, col, num):
        # Check row
        if str(num) in board[row]:
            return False
        
        # Check column
        if str(num) in [board[i][col] for i in range(9)]:
            return False
        
        # Check 3x3 box
        box_row, box_col = 3 * (row // 3), 3 * (col // 3)
        for i in range(box_row, box_row + 3):
            for j in range(box_col, box_col + 3):
                if board[i][j] == str(num):
                    return False
        
        return True
    
    def backtrack():
        for row in range(9):
            for col in range(9):
                if board[row][col] == '.':
                    for num in range(1, 10):
                        if is_valid(row, col, num):
                            board[row][col] = str(num)
                            
                            if backtrack():
                                return True
                            
                            board[row][col] = '.'  # Backtrack
                    
                    return False  # No valid number found
        return True  # Board is complete
    
    backtrack()
    return board

Quiz

Key Takeaways

✅ Backtracking explores solutions by making and undoing choices
✅ Subsets of n elements: 2^n total (include/exclude each)
✅ Permutations of n elements: n! arrangements
✅ N-Queens classic backtracking problem with constraints
✅ Pattern: Make choice → Explore → Backtrack if invalid

Master backtracking for constraint satisfaction and search problems! 🚀