Word Search: Backtracking Pattern

Abstractum

Core Kernel Logic

The Fundamental Principle: Stateful Backtracking

Word Search demonstrates a critical evolution from GroupSum: managing mutable state during recursive exploration, requiring explicit backtracking to restore state after failed attempts.

The Kernel:

• Unlike GroupSum (stateless choices), Word Search modifies a visited array during exploration
• Each cell can be used only once per path, but multiple paths can explore the same cell
• After exploring all directions from a cell, we must restore its state for alternative paths
• Success requires finding ANY path, so we return immediately on first success

The Implementation Pattern:

// CHOOSE
visited[row][col] = true;

// EXPLORE (try all 4 directions)
for (int[] d : DIRECTIONS) {
    if (dfs(nextRow, nextCol, k+1)) {
        visited[row][col] = false;  // UNCHOOSE before returning success
        return true;
    }
}

// BACKTRACK (no path worked)
visited[row][col] = false;
return false;

Why Backtracking is Essential:

• Cell (0,0) might fail in one path but succeed in another path
• Without unmarking, the second path can't use (0,0) even though the first path abandoned it
• Backtracking = temporal state management: "I tried this, it failed, so restore for next attempt"

The Pattern: When recursive exploration modifies shared state, you must undo those modifications when backtracking to allow alternative paths to explore the same state space.

---

The Problem

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

---

Stage 1: Different Problem, Same Pattern Recognition

Designer's first impression: "This looks completely different! It's a grid, not an array."

But wait...

• GroupSum: "At each position, should I USE or SKIP this number?"
• WordSearch: "At each cell, should I EXPLORE or NOT EXPLORE this direction?"

Same pattern! Binary choice, recursive exploration.

---

Stage 2: The Key Difference - Backtracking State

Designer realizes: "In GroupSum, I only change the TARGET. In WordSearch, I'm MODIFYING the board (via visited array)."

This creates a new requirement:

In GroupSum:

• Try using nums[0]
• If it fails, nums[0] is still there, unchanged
• Try skipping nums[0]

In WordSearch:

• Mark cell as visited
• Try all 4 directions
• If all fail, UNMARK the cell (BACKTRACK!)

Why unmark?

Because a different path might need to use this cell!

Example:

W O R D
O R D X

Looking for "WORD":

• Path 1: W→O→R→D (top row) ✓
• If that failed and you didn't unmark, other paths couldn't use those cells

---

Stage 3: The "Return True in Loop" Pattern

This is the pattern that can be tricky:

for (int[] d : DIRECTIONS) {
    if (dfs(board, visited, nextRow, nextCol, word, k + 1)) {
        visited[row][col] = false; // CRITICAL!
        return true;
    }
}

Designer's thought process:

"I'm trying 4 directions. If ANY of them works:

1. I need to UNMARK current cell (because we're leaving)
2. Return success up the chain

If NONE work:

1. I'll unmark AFTER the loop
2. Return false"

Why unmark before returning true?

Because you're LEAVING this path. The cell should be available for other paths.

---

The Complete Word Search Algorithm

private boolean dfs(char[][] board, boolean[][] visited,
    int row, int col, String word, int k) {
    int m = board.length, n = board[0].length;

    // BASE CASES
    // bounds
    if (row < 0 || row >= m || col < 0 || col >= n) return false;

    // already used in this path?
    if (visited[row][col]) return false;

    // must match the k-th character
    if (board[row][col] != word.charAt(k)) return false;

    // last character matched → success
    if (k == word.length() - 1) return true;

    // CHOOSE: Mark as visited
    visited[row][col] = true;

    // EXPLORE: Try all 4 directions
    for (int[] d : DIRECTIONS) {
        int nextRow = row + d[0];
        int nextCol = col + d[1];
        if (dfs(board, visited, nextRow, nextCol, word, k + 1)) {
            visited[row][col] = false; // UNCHOOSE before returning success
            return true;
        }
    }

    // BACKTRACK: Unmark and fail
    visited[row][col] = false;
    return false;
}

---

The Meta-Pattern (Works for BOTH)

Here's the designer's universal framework:

The Backtracking Recipe:

1. BASE CASE: When do I stop making decisions?

• GroupSum: No more numbers
• WordSearch: Found full word OR hit boundary/invalid

2. CHOICE: What are my options at THIS step?

• GroupSum: Use or skip current number
• WordSearch: Explore each of 4 directions

3. EXPLORE: Try each choice

• Make the choice (modify state if needed)
• Recurse with reduced problem
• If successful, return success

4. BACKTRACK: Undo the choice if it failed

• GroupSum: Nothing to undo (didn't modify state)
• WordSearch: Unmark visited cell

5. FAIL: If all choices fail, return false

---

The "Thinking About Returns" Mental Model

You said this is hard. Here's the trick:

STOP

STOP trying to visualize the entire call stack.

Instead, use The Contract Thinking:

// This is a CONTRACT with yourself
boolean canMakeTarget(remaining_array, remaining_target) {
    // "I PROMISE to return true if it's possible,
    //  false if impossible"
}

When you write:

if (canMakeTarget(smaller_problem)) {
    return true;
}

You're saying: "I TRUST that this function upholds its contract for smaller inputs."

The Leap of Faith

This is the leap of faith in recursion.

---

Edge Cases as Understanding Validators

Let's test your understanding:

GroupSum Edge Cases:

Q1: What if nums = [] and target = 0?

• Answer: ?
• Why: ?

Q2: What if nums = [5] and target = 3?

• Answer: ?
• Why: ?

Q3: What if we have duplicates: nums = [2, 2, 4], target = 4?

• Does the algorithm find multiple solutions?
• Does it matter?

WordSearch Edge Cases:

Q1: What if the word is just one letter?

• Where does recursion stop?

Q2: What if we need to use the same cell twice in different paths?

• Does backtracking handle this?

Q3: What if the word requires revisiting a cell (like "AA" in a grid with one 'A')?

• Will this algorithm allow it?
• Should it?

---

Comparison Table

Aspect	GroupSum	WordSearch
State Modified?	No (only target changes)	Yes (visited array)
Backtracking Needed?	No	Yes (unmark visited)
Choices per Step	2 (use/skip)	4 (directions)
Base Case	Out of numbers	Found word or invalid
Return Pattern	Try use → try skip	Try all directions

---

The One Paragraph Summary

Universal Truth

Backtracking is discovering the decision tree by LIVING it. You're not planning all decisions upfront. You make one choice, explore where it leads, and if it fails, you UNDO and try the next choice. The if (recursive_call()) return true pattern means: "I'm checking if this choice leads to success. If yes, propagate success up. If no, try next choice." The hardest mental shift is trusting the recursion without visualizing the stack—just think locally: "What's my choice HERE? Let the recursive call handle the rest."

---

Key Takeaways

1. Pattern Recognition: Many different problems share the same recursive structure
2. State Management: Some problems require backtracking (undoing choices), others don't
3. Trust the Contract: Don't trace the stack; trust that your function works for smaller inputs
4. Local Thinking: Focus on the current decision, not the entire tree
5. Backtracking Template: Choose → Explore → Backtrack → Fail

---

The Discovery Process Summary

The journey from confusion to clarity:

1. ❌ Try to plan all paths upfront → Too complex, exponential paths
2. ❌ Try marking cells without unmarking → Paths block each other
3. 💡 Realize state changes must be reversible
4. 💡 Recognize the Choose-Explore-Unchoose pattern
5. ✅ Mark cell before exploring (CHOOSE)
6. ✅ Try all 4 directions recursively (EXPLORE)
7. ✅ Unmark cell after exploring (BACKTRACK)
8. ✅ Return true immediately on first success (early termination)

The meta-lesson: When recursive exploration modifies shared state, you must explicitly restore that state when backtracking. Stateful recursion requires the Choose-Explore-Unchoose pattern.

---

Summary: The Core Logic Distilled

Essential Understanding

The Problem: Find if a word exists in a grid where each cell can be used only once per path, but different paths can reuse the same cells.

Why Stateless Approaches Fail:

• ❌ Can't just pass parameters like GroupSum - grid state is shared across all recursive calls
• ❌ Marking cells permanently prevents alternative paths from using them
• ❌ Not unmarking creates "ghosts" of failed paths that block successful paths

The Core Insight: Temporal State Management

Each recursive call has a temporal lifecycle for state changes:

Before recursion:  visited[row][col] = false   (available)
During recursion:  visited[row][col] = true    (claimed by this path)
After recursion:   visited[row][col] = false   (released for other paths)

The Choose-Explore-Unchoose Algorithm:

// 1. CHOOSE - Claim the cell
visited[row][col] = true;

// 2. EXPLORE - Try all directions
for (int[] d : DIRECTIONS) {
    if (dfs(nextRow, nextCol, k+1)) {
        visited[row][col] = false;  // UNCHOOSE before success return
        return true;                 // Early termination
    }
}

// 3. UNCHOOSE - Release the cell (backtrack)
visited[row][col] = false;
return false;

Why This Works:

• Each path "owns" its cells temporarily during exploration
• Failed paths release their cells for other paths to try
• Successful paths also release cells (important for cleanup)
• The visited array tracks "currently in use by this path", not "used forever"

Critical Detail - Unmark Before Returning True:

if (dfs(nextRow, nextCol, k+1)) {
    visited[row][col] = false;  // WHY? Cleanup before unwinding
    return true;
}

Because we're unwinding the recursion stack. Each level must clean up its state changes.

The Meta-Pattern: When your recursive exploration modifies shared/global state:

1. Identify what state changes during exploration
2. Make the change before recursing (CHOOSE)
3. Explore all possibilities with that change
4. Restore the original state before returning (UNCHOOSE)
5. This allows alternative paths to explore the same state space

Comparison with GroupSum:

Aspect	GroupSum	WordSearch
State modification	✗ None (only parameters)	✓ Visited array
Backtracking needed	✗ No	✓ Yes (unmark cells)
Choices per step	2 (use/skip)	4 (directions)
State scope	Local (parameters)	Global (shared array)

Complexity:

• Time: O(m × n × 4^L) where L is word length
• Space: O(L) for recursion depth
• State: O(m × n) for visited array

One-Sentence Core: Backtracking with mutable state requires the Choose-Explore-Unchoose pattern to allow failed paths to release resources for alternative paths to explore.

---

Practice Exercise

Try to identify in your next recursive problem:

• What are my choices at each step?
• Do I modify state that needs undoing?
• What's my base case?
• Can I trust my recursive call and think locally?