DSA — Backtracking

What is Backtracking?

An algorithmic technique that builds solutions incrementally and backtracks when a solution fails.

N-Queens Problem

def solve_n_queens(n):
    board = [-1] * n
    
    def is_safe(row, col):
        for i in range(row):
            if board[i] == col or \
               abs(board[i] - col) == abs(i - row):
                return False
        return True
    
    def solve(row):
        if row == n:
            return True
        
        for col in range(n):
            if is_safe(row, col):
                board[row] = col
                if solve(row + 1):
                    return True
                board[row] = -1
        
        return False
    
    solve(0)
    return board

Sudoku Solver

def solve_sudoku(board):
    empty = find_empty(board)
    if not empty:
        return True
    
    row, col = empty
    for num in range(1, 10):
        if is_valid(board, num, row, col):
            board[row][col] = num
            if solve_sudoku(board):
                return True
            board[row][col] = 0
    
    return False

Subset Sum

def subset_sum(arr, target, index=0, current=[]):
    if sum(current) == target:
        return current
    if index >= len(arr) or sum(current) > target:
        return None
    
    # Include current element
    result = subset_sum(arr, target, index + 1, current + [arr[index]])
    if result:
        return result
    
    # Exclude current element
    return subset_sum(arr, target, index + 1, current)

Mini Practice

1. Solve N-Queens
2. Implement Sudoku solver
3. Find all permutations
4. Solve maze problems

Up Next

Continue with Divide and Conquer — divide and conquer strategy.