6a:T4b4,Before implementing a solution, let's understand why backtracking is the right paradigm for this problem. **The Solution Space Structure:** Imagine trying to find the word "HELLO" in a grid. Your solution space looks like a tree: - **Root:** Each cell that contains 'H' is a potential starting point - **Level 1:** From each 'H', each adjacent cell containing 'E' is a potential second step - **Level 2:** From each 'E', each adjacent (unvisited) cell containing 'L' is a potential third step - And so on... This forms a **search tree** where each path from root to leaf represents a sequence of choices. We're looking for a path of length `k` (the word length) where each node's character matches the corresponding character in the word. **Why Not Brute Force?** Theoretically, we could: 1. Generate all possible paths of length `k` starting from any cell 2. Filter paths where the characters spell our word But the number of such paths is astronomical. From each cell, we have up to 4 choices. For a path of length `k`, that's potentially `O(4^k)` paths from each of `m × n` cells. For a 6×6 grid and a 15-character word, that's `36 × 4^15 ≈ 38 billion` potential paths—clearly infeasible.6b:T71e,def exist(board: list[list[str]], word: str) -> bool: """ Determine if word exists in the board using backtracking. Time Complexity: O(m * n * 4^L) where L is the word length Space Complexity: O(L) for the recursion stack """ if not board or not board[0] or not word: return False rows, cols = len(board), len(board[0]) def backtrack(row: int, col: int, index: int) -> bool: # Base case: all characters matched if index == len(word): return True # Boundary and validity check if (row < 0 or row >= rows or col < 0 or col >= cols or board[row][col] != word[index]): return False # CHOOSE: Mark current cell as visited # We use a special character to mark visited cells temp = board[row][col] board[row][col] = '#' # Mark as visited # EXPLORE: Try all four directions directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] for dr, dc in directions: if backtrack(row + dr, col + dc, index + 1): return True # Found the word! # UNCHOOSE: Restore the cell (backtrack) board[row][col] = temp return False # Try starting from every cell in the grid for i in range(rows): for j in range(cols): if board[i][j] == word[0]: # Optimization: only start from matching cells if backtrack(i, j, 0): return True return False # Example usage board = [ ["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"] ] print(exist(board, "ABCCED")) # True print(exist(board, "SEE")) # True print(exist(board, "ABCB")) # False (would require revisiting B)6c:T800,function exist(board: string[][], word: string): boolean { /** * Determine if word exists in the board using backtracking. * * Time Complexity: O(m * n * 4^L) where L is the word length * Space Complexity: O(L) for the recursion stack */ if (!board.length || !board[0].length || !word.length) { return false; } const rows = board.length; const cols = board[0].length; const backtrack = (row: number, col: number, index: number): boolean => { // Base case: all characters matched if (index === word.length) { return true; } // Boundary and validity check if (row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] !== word[index]) { return false; } // CHOOSE: Mark current cell as visited const temp = board[row][col]; board[row][col] = '#'; // Mark as visited // EXPLORE: Try all four directions const directions: [number, number][] = [[0, 1], [0, -1], [1, 0], [-1, 0]]; for (const [dr, dc] of directions) { if (backtrack(row + dr, col + dc, index + 1)) { return true; // Found the word! } } // UNCHOOSE: Restore the cell (backtrack) board[row][col] = temp; return false; }; // Try starting from every cell in the grid for (let i = 0; i < rows; i++) { for (let j = 0; j < cols; j++) { if (board[i][j] === word[0]) { // Optimization: only start from matching cells if (backtrack(i, j, 0)) { return true; } } } } return false; } // Example usage const board = [ ["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"] ]; console.log(exist(board, "ABCCED")); // true console.log(exist(board, "SEE")); // true console.log(exist(board, "ABCB")); // false6d:T981,public class WordSearch { private char[][] board; private int rows, cols; private String word; /** * Determine if word exists in the board using backtracking. * * Time Complexity: O(m * n * 4^L) where L is the word length * Space Complexity: O(L) for the recursion stack */ public boolean exist(char[][] board, String word) { if (board == null || board.length == 0 || word == null || word.isEmpty()) { return false; } this.board = board; this.word = word; this.rows = board.length; this.cols = board[0].length; // Try starting from every cell in the grid for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (board[i][j] == word.charAt(0)) { // Optimization if (backtrack(i, j, 0)) { return true; } } } } return false; } private boolean backtrack(int row, int col, int index) { // Base case: all characters matched if (index == word.length()) { return true; } // Boundary and validity check if (row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] != word.charAt(index)) { return false; } // CHOOSE: Mark current cell as visited char temp = board[row][col]; board[row][col] = '#'; // Mark as visited // EXPLORE: Try all four directions int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; for (int[] dir : directions) { if (backtrack(row + dir[0], col + dir[1], index + 1)) { return true; // Found the word! } } // UNCHOOSE: Restore the cell (backtrack) board[row][col] = temp; return false; } public static void main(String[] args) { WordSearch ws = new WordSearch(); char[][] board = { {'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'} }; System.out.println(ws.exist(board, "ABCCED")); // true System.out.println(ws.exist(board, "SEE")); // true System.out.println(ws.exist(board, "ABCB")); // false } }6e:T53d,Understanding the complexity of backtracking algorithms is crucial but often tricky. Let's analyze our Word Search solution carefully. **Time Complexity: O(m × n × 4^L)** Where: - `m` = number of rows - `n` = number of columns - `L` = length of the word **Derivation:** 1. **Starting points:** We potentially start from each of the `m × n` cells 2. **Branching factor:** From each cell, we explore up to 4 directions 3. **Depth:** We recurse up to `L` levels (the word length) 4. **Work per call:** O(1) for bounds check and character comparison At first glance, this suggests `O(m × n × 4^L)`. But wait—we said 4 directions, yet after the first step, we can't go back to where we came from (it's marked visited). So the actual branching factor is closer to 3 after the first step. However, we traditionally express this as `O(4^L)` because: - The first step truly has 4 options - Using 3 instead gives O(4 × 3^(L-1)), which is still O(4^L) asymptotically - The constant factor difference doesn't affect big-O **Space Complexity: O(L)** The space complexity is determined by: 1. **Recursion stack:** Maximum depth is `L` (the word length) 2. **Board modification:** We modify the board in-place, using O(1) extra space If we used a separate `visited` matrix, space would be O(m × n), but our in-place marking avoids this.6f:T4be,While our basic solution is correct and reasonably efficient, several optimizations can dramatically improve performance for challenging inputs. **Optimization 1: Character Frequency Check (Pre-pruning)** Before starting the search, verify that the grid contains at least as many of each character as the word requires: ```python from collections import Counter def exist_optimized(board, word): # Count characters in board board_count = Counter(char for row in board for char in row) word_count = Counter(word) # Early termination if word can't possibly exist for char, count in word_count.items(): if board_count[char] < count: return False # ... proceed with backtracking ``` This O(m × n + L) preprocessing step can immediately return `False` for impossible cases. **Optimization 2: Reverse Word Search** If the last character of the word is rarer in the grid than the first character, search for the reversed word instead: ```python if board_count[word[0]] > board_count[word[-1]]: word = word[::-1] # Search backwards ``` This doesn't change the worst case but significantly improves average case by reducing the number of starting points.70:T69c,from collections import Counter def exist_optimized(board: list[list[str]], word: str) -> bool: """ Optimized word search with pre-pruning and reverse search. """ if not board or not board[0] or not word: return False rows, cols = len(board), len(board[0]) # Optimization 1: Character frequency pre-check board_count = Counter(char for row in board for char in row) word_count = Counter(word) for char, count in word_count.items(): if board_count.get(char, 0) < count: return False # Word can't possibly exist # Optimization 2: Start from the rarer end if board_count[word[0]] > board_count[word[-1]]: word = word[::-1] def backtrack(row: int, col: int, index: int) -> bool: if index == len(word): return True if (row < 0 or row >= rows or col < 0 or col >= cols or board[row][col] != word[index]): return False temp = board[row][col] board[row][col] = '#' # Optimization 3: Order directions by likelihood (can be problem-specific) found = (backtrack(row + 1, col, index + 1) or backtrack(row - 1, col, index + 1) or backtrack(row, col + 1, index + 1) or backtrack(row, col - 1, index + 1)) board[row][col] = temp return found # Only try starting positions that match first character for i in range(rows): for j in range(cols): if board[i][j] == word[0]: if backtrack(i, j, 0): return True return False71:T53b,The Word Search problem has many variations that test different aspects of backtracking mastery. Understanding these prepares you for interview variations and real-world applications. **Variation 1: Word Search II (Find All Words)** Given a list of words instead of a single word, find all words that exist in the grid. The naive approach would run Word Search for each word, but a Trie-based approach is much more efficient: - Build a Trie from all target words - Run backtracking once, checking the Trie at each step - Remove found words from the Trie to avoid duplicates This reduces time from O(W × m × n × 4^L) to O(m × n × 4^L') where W is the number of words and L' is the maximum word length. **Variation 2: Counting All Occurrences** Instead of just determining if a word exists, count how many distinct paths spell the word: ```python def count_occurrences(board, word): count = 0 def backtrack(row, col, index): nonlocal count if index == len(word): count += 1 return # Don't return True—continue searching # ... same logic but don't return early on success # ... search from all cells return count ``` The key difference: we don't return immediately when we find a match; we increment a counter and continue to find all matches.63:{"json":{"id":"seed_4941c806544f8d14ca4b1384b45f51de","slug":"common-backtracking-patterns","category":"Data Structures & Algorithms","topic":"Common Backtracking Patterns","title":"Common Backtracking Patterns","description":"Master the most frequently encountered backtracking problem patterns including word search in grids, combination sum problems, palindrome partitioning, and valid parentheses generation. Build a comprehensive library of backtracking solutions that prepare you for any systematic exploration challenge.","difficulty":"INTERMEDIATE","estimatedMinutes":90,"pages":[{"id":"seed_d373497adb9d5a81a233ef2dbe489c89","title":"Word Search in Grid","order":0,"content":[{"id":"opening-hook","title":"The Grid Navigation Challenge","content":[{"data":{"content":"Imagine you're looking at a crossword puzzle, but instead of reading clues, you need to verify whether a given word exists somewhere in the grid. The word might wind its way through the grid in any direction—horizontally, vertically, or diagonally—turning at each cell to find its path. This is the **Word Search problem**, a quintessential backtracking challenge that appears across software engineering domains from game development to text processing to bioinformatics.\n\nThe Word Search problem is deceptively simple to state but profoundly instructive in its solution. It exemplifies how backtracking transforms what could be an intractable brute-force exploration into a structured, efficient search through a solution space. By mastering this problem, you gain intuition that transfers directly to countless grid-based exploration challenges."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand the Word Search problem completely, including its formal definition, why backtracking is the natural solution, how to implement it with optimal pruning, and how to analyze its complexity. You'll see the standard template in action and understand how to adapt it for variations like finding all occurrences or searching for multiple words.","variant":"info"},"type":"callout"}]},{"id":"problem-definition","title":"Formal Problem Statement","content":[{"data":{"content":"Let us establish the problem with mathematical precision before exploring solutions.\n\n**The Word Search Problem:**\n\nGiven:\n- An `m × n` grid of characters `board[m][n]`\n- A string `word` of length `k`\n\nDetermine whether `word` exists in the grid, where the word can be constructed from letters of sequentially adjacent cells, and the same cell may not be used more than once.\n\n**Adjacency Definition:**\n\nTwo cells are \"adjacent\" if they share an edge. This means each cell (except those on the boundary) has exactly 4 neighbors: up, down, left, and right. Importantly, diagonal cells are **not** adjacent in the standard formulation.\n\n**Constraints:**\n- `1 ≤ m, n ≤ 6` (for the LeetCode variant)\n- `1 ≤ word.length ≤ 15`\n- `board` and `word` consist of only lowercase and uppercase English letters\n\nThe constraint sizes hint at the exponential nature of the problem—the solution space is too large for polynomial algorithms but small enough that pruned backtracking works efficiently."},"type":"text"},{"data":{"input":"board = [[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]], word = \"ABCCED\"","title":"Visualizing the Word Search","output":"true","description":"Consider searching for the word \"ABCCED\" in the following grid:","explanation":"The path A(0,0) → B(0,1) → C(0,2) → C(1,2) → E(2,2) → D(2,1) spells \"ABCCED\". Notice how the path turns downward at C, then moves down again to E, then left to D. The path must be contiguous with each step moving to an adjacent cell."},"type":"example"},{"data":{"icon":"Info","title":"The No-Revisit Constraint","content":"A critical constraint is that each cell can only be used once per path. This prevents trivial solutions like bouncing between two adjacent cells to form words like \"ABAB\". This constraint is what makes the problem a true backtracking challenge—we must track our path and undo our choices when backtracking.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"why-backtracking","title":"Why Backtracking Is the Natural Solution","content":[{"data":{"content":"$6a"},"type":"text"},{"data":{"items":["**Early Pruning** — If the first character doesn't match, we don't explore from that cell at all. If the second character doesn't match, we abandon that path immediately. This cuts off entire subtrees of the search space.","**Structured Exploration** — Rather than generating all paths then filtering, we build paths incrementally, checking validity at each step. Invalid prefixes are never extended.","**Implicit Memoization** — The visited array ensures we never revisit cells in the current path, preventing infinite loops and redundant exploration.","**Directional Focus** — We only explore 4 directions at each step, not arbitrary jumps. This bounds the branching factor to a constant."],"title":{"icon":"Zap","text":"What Makes Backtracking Efficient","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"icon":"Lightbulb","title":"The Power of Pruning","content":"In practice, the backtracking solution is much faster than the theoretical worst case suggests. For random grids and words, most paths are pruned within the first few characters because the next character simply doesn't match. The solution's efficiency comes not from being polynomial, but from aggressive pruning that makes the average case far better than the worst case.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"backtracking-template-applied","title":"Applying the Backtracking Template","content":[{"data":{"content":"Recall the universal backtracking template from earlier in this chapter:\n\n```\nfunction backtrack(state):\n if isComplete(state):\n processResult()\n return\n \n for choice in getChoices(state):\n if isValid(choice, state):\n make(choice) // Choose\n backtrack(newState) // Explore\n undo(choice) // Unchoose\n```\n\nLet's map this template to the Word Search problem:\n\n**State:** Our current position `(row, col)` in the grid and the current index `i` in the word we're trying to match.\n\n**isComplete:** We've matched all characters, i.e., `i == word.length`.\n\n**getChoices:** The four adjacent cells: `(row-1, col)`, `(row+1, col)`, `(row, col-1)`, `(row, col+1)`.\n\n**isValid:** The cell is within bounds, hasn't been visited in the current path, and its character matches `word[i]`.\n\n**make(choice):** Mark the cell as visited.\n\n**undo(choice):** Unmark the cell as visited (the critical backtracking step)."},"type":"text"},{"data":{"fileName":"word_search.py","languages":[{"code":"$6b","label":"Python","value":"python"},{"code":"$6c","label":"TypeScript","value":"typescript"},{"code":"$6d","label":"Java","value":"java"}]},"type":"code"}],"titleType":"number","titleNumber":3},{"id":"deep-dive-algorithm","title":"Deep Dive: Understanding Each Component","content":[{"data":{"content":"Let's dissect each component of our solution to understand the nuances that make it work correctly and efficiently.\n\n**The Visited-Cell Strategy:**\n\nNotice that we don't use a separate `visited` set or matrix. Instead, we temporarily modify the board itself by replacing the current cell's character with a sentinel value (`'#'`). This is a common optimization:\n\n1. **Constant-time marking:** `board[row][col] = '#'` is O(1)\n2. **Space efficiency:** No additional O(m×n) visited matrix needed\n3. **Automatic propagation:** The modification is visible to all recursive calls\n4. **Easy restoration:** We save the original character and restore it during backtracking\n\nThis technique is safe because we never look at the *value* of a '#' cell—we only check if the character matches the word, which '#' never will (assuming the word contains only letters)."},"type":"text"},{"data":{"icon":"AlertCircle","title":"When In-Place Marking Fails","content":"This optimization only works if the sentinel character cannot appear in the word. If the word could contain '#', you'd need a separate visited structure. In competitive programming, always verify the input character set before using this trick.","variant":"warning"},"type":"callout"},{"data":{"content":"**The Order of Checks:**\n\nOur validity check combines multiple conditions:\n\n```python\nif (row < 0 or row >= rows or \n col < 0 or col >= cols or \n board[row][col] != word[index]):\n return False\n```\n\nThe order matters for short-circuit evaluation:\n1. **Bounds check first:** Accessing `board[row][col]` with invalid indices would crash\n2. **Character match last:** Only checked if we're in bounds\n\nThe character match implicitly handles the visited check—a visited cell contains '#', which won't match any letter in the word.\n\n**The Direction Array Pattern:**\n\n```python\ndirections = [(0, 1), (0, -1), (1, 0), (-1, 0)] # right, left, down, up\n```\n\nThis is a classic pattern for grid traversal. Each tuple represents (row_delta, col_delta). Using an array instead of four separate recursive calls:\n- Makes the code cleaner and more maintainable\n- Makes it trivial to add diagonal movement (just add 4 more tuples)\n- Enables easy direction ordering for problems where it matters"},"type":"text"},{"data":{"items":["**Return early on success** — Once we find the word, we immediately return `True` without exploring further paths. This is critical for efficiency since we only need one valid path.","**Outer loop optimization** — We only attempt to start backtracking from cells whose character matches `word[0]`. This simple check can eliminate most cells from consideration.","**Recursion naturally handles path length** — The `index` parameter tracks how many characters we've matched. When `index == len(word)`, we've matched all characters.","**No explicit path storage** — We don't need to store the actual path unless the problem asks for it. The recursion stack implicitly represents the current path."],"title":{"icon":"CheckCircle","text":"Key Implementation Insights","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"}],"titleType":"number","titleNumber":4},{"id":"complexity-analysis","title":"Rigorous Complexity Analysis","content":[{"data":{"content":"$6e"},"type":"text"},{"data":{"rows":[["Outer loops (starting points)","O(m × n)","Try each cell as potential start"],["Backtracking tree depth","O(L)","Maximum word length determines depth"],["Branching factor","O(4) per level","4 directions from each cell"],["Work per node","O(1)","Constant-time checks"],["Total time (worst case)","O(m × n × 4^L)","All components multiplied"],["Space (recursion)","O(L)","Stack frames for word length"]],"caption":"Complexity Breakdown by Component","headers":["Component","Complexity","Explanation"]},"type":"table"},{"data":{"icon":"Zap","title":"Practical Performance","content":"In practice, the algorithm runs much faster than the worst-case bound suggests. Early pruning—especially when the first character doesn't match—eliminates vast portions of the search space. For random grids with uniform character distribution, the expected time is much closer to O(m × n) for most words that don't exist in the grid.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"advanced-optimizations","title":"Advanced Optimizations and Pruning Strategies","content":[{"data":{"content":"$6f"},"type":"text"},{"data":{"fileName":"word_search_optimized.py","languages":[{"code":"$70","label":"Python","value":"python"}]},"type":"code"},{"data":{"items":["**Iterative deepening** — For very long words, search incrementally: first check if a path of length 1 exists, then length 2, etc. This catches failures faster for words that fail on early characters.","**Trie-based multi-word search** — When searching for multiple words, use a Trie. This is the approach used in 'Word Search II' and avoids redundant exploration.","**Bitmask visited tracking** — For very small boards, use an integer bitmask instead of modifying the board. This can be faster due to cache efficiency.","**Parallel starting points** — In production systems, different starting points can be explored in parallel, with early termination shared across threads."],"title":{"icon":"Zap","text":"Additional Optimization Ideas","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"titleType":"number","titleNumber":6},{"id":"variations-extensions","title":"Problem Variations and Extensions","content":[{"data":{"content":"$71"},"type":"text"},{"data":{"left":[{"data":{"items":["**LeetCode 79:** Word Search (the classic)","**LeetCode 212:** Word Search II (multiple words)","**LeetCode 1254:** Number of Closed Islands","**LeetCode 200:** Number of Islands","**LeetCode 130:** Surrounded Regions"],"title":{"icon":"Target","text":"Related Problems","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["**Puzzle Games:** Wordle, Crosswords, Boggle","**Bioinformatics:** DNA sequence matching","**Image Processing:** Pattern recognition in pixel grids","**OCR Systems:** Character sequence detection","**Game AI:** Pathfinding in tile-based games"],"title":{"icon":"Lightbulb","text":"Real-World Applications","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"icon":"Info","title":"The Boggle Connection","content":"The Word Search problem is essentially a simplified version of the game Boggle, where players find words on a 4×4 grid of letter dice. The main differences: Boggle typically allows diagonal moves and has a time limit. Understanding Word Search prepares you to build a Boggle solver—a fun weekend project!","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary","title":"Summary: Mastering Grid-Based Backtracking","content":[{"data":{"content":"The Word Search problem is a foundational example of how backtracking elegantly solves grid exploration problems. Let's consolidate the key insights:"},"type":"text"},{"data":{"type":"ordered","items":["**The problem maps directly to the backtracking template** — Choose a direction, explore recursively, unchoose by unmarking visited cells.","**In-place board modification** serves dual purpose — Marks cells as visited without extra space, and automatically prevents revisits since the sentinel character won't match.","**Early pruning is the key to efficiency** — Checking character matches at each step eliminates vast portions of the exponential search space.","**Complexity is exponential but manageable** — O(m × n × 4^L) sounds scary, but practical inputs have small L, and pruning makes average case much better.","**Optimizations compound** — Pre-checking character frequencies, reversing the word, and careful direction ordering can dramatically speed up the algorithm.","**The pattern generalizes** — Any path-finding problem in a grid with constraints can be approached similarly."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's next:**\n\nWith grid-based backtracking mastered, we'll explore the **Combination Sum** family of problems—a different flavor of backtracking where we build numeric combinations that sum to a target. These problems introduce new concerns like handling duplicates and optimizing the choice generation process."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now have a deep understanding of grid-based backtracking through the Word Search problem. This pattern—exploring a 2D space with constraint checking and path tracking—appears in countless problems. Practice implementing variations to solidify your understanding before moving on.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_91f6ebb10da81c599d62270011efcf20","title":"Combination Sum Problems","order":1,"content":null,"isLocked":true},{"id":"seed_86d5c3d63355914886a1c08b3bfd3e56","title":"Palindrome Partitioning","order":2,"content":null,"isLocked":true},{"id":"seed_61bc6053e76859d46b45ba09b9b44904","title":"Valid Parentheses Generation","order":3,"content":null,"isLocked":true}]}}