🔙 Backtracking Fundamentals

🎯 What is Backtracking?

Backtracking is a recursive algorithmic technique for solving problems incrementally by trying partial solutions and abandoning them if they fail to satisfy the constraints. It's a form of depth-first search with pruning.

Core Idea: Build a solution step by step, undoing steps that lead to dead ends
Key Properties: Recursive, exhaustive search with pruning
When to Use: Constraint satisfaction, combinatorial problems
vs. Brute Force: Backtracking prunes invalid paths early

📌 Recursive DFS📌 Branch & Bound📌 Constraint Propagation

The Core Idea

Key Insight: Backtracking explores all possible solutions systematically. When it encounters a partial solution that cannot be completed to a valid solution, it "backtracks" and tries a different path.

Three Steps:

1. Choose Select a candidate for the current position
2. Explore Recursively try to complete the solution
3. Unchoose Undo the choice and try alternatives

# Backtracking - The General Pattern
def backtrack(candidate):
    if is_solution(candidate):
        process_solution(candidate)
        return
    
    for next_candidate in get_candidates(candidate):
        if is_valid(next_candidate):
            place(next_candidate)  # Make a choice
            backtrack(next_candidate)  # Recurse
            remove(next_candidate)  # Undo the choice (backtrack)

# Classic Example: Generating all permutations
def permute(nums):
    result = []
    
    def backtrack(path):
        if len(path) == len(nums):
            result.append(path[:])
            return
        
        for num in nums:
            if num not in path:
                path.append(num)
                backtrack(path)
                path.pop()  # Backtrack!
    
    backtrack([])
    return result

📝 The Backtracking Template

🎯 Universal Backtracking Pattern

Most backtracking problems follow a similar structure. Understanding this template helps solve any backtracking problem.

Base Case: When to stop recursing
Candidate Generation: What choices are available
Validity Check: Does the choice satisfy constraints
Backtrack: Undo the choice to try alternatives

# Complete Backtracking Template
class Backtracking:
    def solve(self):
        self.result = []
        self.backtrack([], 0)
        return self.result
    
    def backtrack(self, path, start):
        # Base case: found a complete solution
        if self.is_solution(path):
            self.result.append(path[:])  # Make a copy!
            return
        
        # Iterate through candidates
        for i in range(start, self.n):
            if self.is_valid(path, i):
                # Choose
                path.append(self.candidates[i])
                
                # Explore
                self.backtrack(path, i + 1)  # or i for combinations with repetition
                
                # Unchoose (Backtrack)
                path.pop()
    
    def is_solution(self, path):
        # Define when a path is complete
        return len(path) == self.target_length
    
    def is_valid(self, path, candidate_index):
        # Define constraints
        return True

# Key Variations:
# - Permutations: different ordering, use used[] array
# - Combinations: start index prevents duplicates
# - Subsets: include/exclude each element
# - N-Queens: check row/col/diagonal constraints

🔄 Permutations

🎯 All Possible Orderings

Generate all permutations of a given array (or string). Each element appears exactly once in each permutation.

N! Permutations: For n elements, there are n! permutations
Approach: Use a used array to track which elements are selected
Time Complexity: O(n × n!)

# Permutations of an Array
def permute(nums):
    result = []
    used = [False] * len(nums)
    
    def backtrack(path):
        if len(path) == len(nums):
            result.append(path[:])
            return
        
        for i in range(len(nums)):
            if not used[i]:
                used[i] = True
                path.append(nums[i])
                backtrack(path)
                path.pop()
                used[i] = False
    
    backtrack([])
    return result

# Permutations with Duplicates
def permute_unique(nums):
    nums.sort()
    result = []
    used = [False] * len(nums)
    
    def backtrack(path):
        if len(path) == len(nums):
            result.append(path[:])
            return
        
        for i in range(len(nums)):
            if used[i]:
                continue
            # Skip duplicates
            if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                continue
            
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False
    
    backtrack([])
    return result

# Example:
# permute([1,2,3]) → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

📊 Combinations

🎯 All Subsets of Size K

Generate all combinations of k elements from an array of n elements. Order doesn't matter, and each element appears at most once.

Number of Combinations: C(n, k) = n! / (k! × (n-k)!)
Approach: Use a start index to avoid duplicates
Key Insight: Combinations are unordered subsets

# Combinations of Size K
def combine(n, k):
    result = []
    
    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
        
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(1, [])
    return result

# Combinations from an Array
def combine_array(nums, k):
    result = []
    
    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
        
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(0, [])
    return result

# Example:
# combine(4, 2) → [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
# combine_array([1,2,3,4], 2) → [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

📐 Subsets (Power Set)

🎯 All Subsets (Including Empty Set)

Generate all possible subsets of a given set. This includes the empty set and the set itself.

Number of Subsets: 2^n
Approach 1: Include/Exclude each element (recursive)
Approach 2: Iterative with start index

# All Subsets (Power Set)
def subsets(nums):
    result = []
    
    # Approach 1: Include/Exclude (clean recursion)
    def backtrack(i, path):
        if i == len(nums):
            result.append(path[:])
            return
        
        # Exclude current element
        backtrack(i + 1, path)
        
        # Include current element
        path.append(nums[i])
        backtrack(i + 1, path)
        path.pop()
    
    backtrack(0, [])
    return result

# All Subsets (Iterative start index approach)
def subsets_iterative(nums):
    result = [[]]
    
    for num in nums:
        result += [curr + [num] for curr in result]
    
    return result

# Subsets with Duplicates
def subsets_with_dup(nums):
    nums.sort()
    result = []
    
    def backtrack(start, path):
        result.append(path[:])
        
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(0, [])
    return result

# Example:
# subsets([1,2,3]) → [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

♛ N-Queens Problem

🎯 Place N Queens on N×N Board

Place N queens on an N×N chessboard so that no two queens threaten each other (same row, column, or diagonal).

Constraint: No two queens share row, column, or diagonal
Approach: Place queens row by row, checking columns and diagonals
Time: O(N!) factorial

# N-Queens Problem
def solve_n_queens(n):
    result = []
    board = [['.'] * n for _ in range(n)]
    cols = set()
    diag1 = set()  # r - c (main diagonal)
    diag2 = set()  # r + c (anti-diagonal)
    
    def backtrack(row):
        if row == n:
            result.append([''.join(row) for row in board])
            return
        
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            
            # Place queen
            board[row][col] = 'Q'
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            
            backtrack(row + 1)
            
            # Backtrack
            board[row][col] = '.'
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)
    
    backtrack(0)
    return result

# Example:
# solve_n_queens(4) → 2 solutions
# [['.Q..', '...Q', 'Q...', '..Q.'],
#  ['..Q.', 'Q...', '...Q', '.Q..']]

# Count solutions (no board representation)
def total_n_queens(n):
    cols = [0] * n
    diag1 = [0] * (2 * n - 1)
    diag2 = [0] * (2 * n - 1)
    count = 0
    
    def backtrack(row):
        nonlocal count
        if row == n:
            count += 1
            return
        
        for col in range(n):
            if cols[col] or diag1[row - col + n - 1] or diag2[row + col]:
                continue
            
            cols[col] = diag1[row - col + n - 1] = diag2[row + col] = 1
            backtrack(row + 1)
            cols[col] = diag1[row - col + n - 1] = diag2[row + col] = 0
    
    backtrack(0)
    return count

🧩 Sudoku Solver

🎯 Solve a 9×9 Sudoku Puzzle

Fill the empty cells in a Sudoku board following the rules: each row, column, and 3×3 subgrid must contain digits 1-9 exactly once.

Constraints: Row, column, and box constraints
Approach: Find empty cell, try each digit 1-9
Optimization: Choose cells with fewest options (MRV)

# Sudoku Solver
def solve_sudoku(board):
    def is_valid(board, row, col, num):
        # Check row
        for j in range(9):
            if board[row][j] == num:
                return False
        
        # Check column
        for i in range(9):
            if board[i][col] == num:
                return False
        
        # Check 3x3 box
        box_row = (row // 3) * 3
        box_col = (col // 3) * 3
        for i in range(box_row, box_row + 3):
            for j in range(box_col, box_col + 3):
                if board[i][j] == num:
                    return False
        
        return True
    
    def find_empty(board):
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    return (i, j)
        return None
    
    def backtrack(board):
        empty = find_empty(board)
        if not empty:
            return True
        
        row, col = empty
        for num in map(str, range(1, 10)):
            if is_valid(board, row, col, num):
                board[row][col] = num
                
                if backtrack(board):
                    return True
                
                board[row][col] = '.'
        
        return False
    
    backtrack(board)
    return board

# Example:
board = [
    ['5','3','.','.','7','.','.','.','.'],
    ['6','.','.','1','9','5','.','.','.'],
    ['.','9','8','.','.','.','.','6','.'],
    ['8','.','.','.','6','.','.','.','3'],
    ['4','.','.','8','.','3','.','.','1'],
    ['7','.','.','.','2','.','.','.','6'],
    ['.','6','.','.','.','.','2','8','.'],
    ['.','.','.','4','1','9','.','.','5'],
    ['.','.','.','.','8','.','.','7','9']
]

🐴 Knight's Tour

🎯 Visit Every Square Exactly Once

A knight moves in an L-shape (2+1). The Knight's Tour visits every square on an N×N board exactly once.

Moves: 8 possible moves for a knight
Approach: Try each move, backtrack if dead end
Warnsdorff's Rule: Always move to the square with fewest onward moves

# Knight's Tour (Backtracking)
def knights_tour(n):
    board = [[-1] * n for _ in range(n)]
    
    # Knight moves (8 possible)
    moves = [
        (2, 1), (1, 2), (-1, 2), (-2, 1),
        (-2, -1), (-1, -2), (1, -2), (2, -1)
    ]
    
    def is_valid(x, y):
        return 0 <= x < n and 0 <= y < n and board[x][y] == -1
    
    def backtrack(x, y, move_num):
        if move_num == n * n:
            return True
        
        for dx, dy in moves:
            nx, ny = x + dx, y + dy
            if is_valid(nx, ny):
                board[nx][ny] = move_num
                if backtrack(nx, ny, move_num + 1):
                    return True
                board[nx][ny] = -1
        
        return False
    
    # Start from (0, 0)
    board[0][0] = 0
    if backtrack(0, 0, 1):
        return board
    return None

# Warnsdorff's Rule (Optimized)
def knights_tour_warnsdorff(n):
    # Implementation with heuristic for better performance
    pass

# Example:
# knights_tour(8) finds a complete tour on 8x8 board

🔍 Word Search

🎯 Find Words in a Grid

Search for a word in a 2D grid of letters. You can move in 4 directions (up, down, left, right) and can't reuse the same letter.

Constraints: Adjacent cells, no reuse
Approach: DFS from each cell that matches first letter
Complexity: O(N × 3^L) where L = word length

# Word Search
def word_search(board, word):
    m, n = len(board), len(board[0])
    
    def dfs(i, j, k):
        if k == len(word):
            return True
        
        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]:
            return False
        
        # Mark as visited
        temp = board[i][j]
        board[i][j] = '#'
        
        # Explore 4 directions
        found = (dfs(i+1, j, k+1) or dfs(i-1, j, k+1) or
                 dfs(i, j+1, k+1) or dfs(i, j-1, k+1))
        
        # Backtrack
        board[i][j] = temp
        return found
    
    for i in range(m):
        for j in range(n):
            if board[i][j] == word[0] and dfs(i, j, 0):
                return True
    
    return False

# Example:
board = [
    ['A','B','C','E'],
    ['S','F','C','S'],
    ['A','D','E','E']
]
# word_search(board, "ABCCED") → True
# word_search(board, "SEE") → True
# word_search(board, "ABCB") → False

🎯 Combination Sum

🎯 Find All Combinations that Sum to Target

Given an array of distinct numbers, find all unique combinations that sum to a target value. Numbers can be used unlimited times.

Type 1: Unlimited use (combination sum I)
Type 2: Each number once (combination sum II)
Type 3: Any length (combination sum III)

# Combination Sum I (Unlimited use)
def combination_sum(candidates, target):
    result = []
    candidates.sort()
    
    def backtrack(start, remaining, path):
        if remaining == 0:
            result.append(path[:])
            return
        
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
            path.append(candidates[i])
            backtrack(i, remaining - candidates[i], path)  # i not i+1
            path.pop()
    
    backtrack(0, target, [])
    return result

# Combination Sum II (Each once, no duplicates)
def combination_sum2(candidates, target):
    result = []
    candidates.sort()
    
    def backtrack(start, remaining, path):
        if remaining == 0:
            result.append(path[:])
            return
        
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
            if i > start and candidates[i] == candidates[i-1]:
                continue
            path.append(candidates[i])
            backtrack(i + 1, remaining - candidates[i], path)
            path.pop()
    
    backtrack(0, target, [])
    return result

# Example:
# combination_sum([2,3,6,7], 7) → [[2,2,3],[7]]
# combination_sum2([10,1,2,7,6,1,5], 8) → [[1,1,6],[1,2,5],[1,7],[2,6]]

✂️ Pruning & Optimization

🎯 Making Backtracking Efficient

Sorting: Sort candidates to prune early (e.g., combination sum)
Memoization: Cache results for subproblems
Constraint Propagation: Reduce search space using constraints
Most Constrained Variable: Choose variable with fewest options first
Forward Checking: Prune branches when constraints are violated

# Pruning Examples

# 1. Sort for early break
def combination_sum_pruned(candidates, target):
    result = []
    candidates.sort()  # Sort for pruning
    # ... rest of algorithm with break when candidates[i] > remaining

# 2. Memoization for repeated subproblems
from functools import lru_cache
def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    
    @lru_cache(None)
    def dfs(i, target):
        if target == 0:
            return True
        if i >= len(nums) or target < 0:
            return False
        
        return dfs(i + 1, target) or dfs(i + 1, target - nums[i])
    
    return dfs(0, total // 2)

# 3. MRV (Minimum Remaining Values) - choose variable with fewest choices
# Used in Sudoku solvers and CSPs

# 4. Constraint Propagation
# In N-Queens: if a queen is placed, mark entire row, col, diagonal as invalid
# Reduces the search space significantly

⏱️ Time & Space Complexities

Problem	Time Complexity	Space Complexity	Notes
Permutations	O(n × n!)	O(n!)	n elements
Combinations	O(C(n,k) × k)	O(C(n,k) × k)	choose k from n
Subsets	O(2^n × n)	O(2^n × n)	power set
N-Queens	O(N!)	O(N²)	N queens
Sudoku	O(9^(N²))	O(N²)	N=9
Knight's Tour	O(8^(N²))	O(N²)	exponential
Word Search	O(N × 3^L)	O(L)	L = word length
Combination Sum	O(2^target)	O(target)	with pruning

🌍 Real-World Applications

AI & Game Playing: Chess, Sudoku solvers, puzzle games
Constraint Satisfaction: Scheduling, resource allocation
Circuit Design: Satisfiability, verification
Bioinformatics: DNA sequencing, protein folding
Network Routing: Path finding with constraints
Compiler Design: Syntax analysis, parsing
Cryptography: Constraint solving, SAT solvers
Robotics: Path planning, motion planning

📝 Interview Patterns & Problems

🎯 Key Interview Questions

Classic: "Generate all permutations/combinations/subsets"
N-Queens: "Place N queens on N×N board"
Sudoku: "Solve a Sudoku puzzle"
Word Search: "Find word in a grid"
Combination Sum: "Find all combinations that sum to target"
Letter Case Permutation: "Generate all letter case permutations"
Palindrome Partitioning: "Partition string into palindromes"
Phone Number: "Letter combinations from phone number"
Generate Parentheses: "Valid parentheses combinations"

# Quick Interview Problem: Generate Parentheses
def generate_parenthesis(n):
    result = []
    
    def backtrack(open_count, close_count, path):
        if open_count == close_count == n:
            result.append(path)
            return
        
        if open_count < n:
            backtrack(open_count + 1, close_count, path + '(')
        if close_count < open_count:
            backtrack(open_count, close_count + 1, path + ')')
    
    backtrack(0, 0, '')
    return result

# Example:
# generate_parenthesis(3) → ["((()))","(()())","(())()","()(())","()()()"]

# Quick Interview Problem: Letter Combinations of a Phone Number
def letter_combinations(digits):
    if not digits:
        return []
    
    mapping = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    result = []
    
    def backtrack(i, path):
        if i == len(digits):
            result.append(path)
            return
        
        for char in mapping[digits[i]]:
            backtrack(i + 1, path + char)
    
    backtrack(0, '')
    return result