Backtracking Practice Problems

Problem 1: Word Search

Statement: Given a 2D grid of characters and a target word, determine if the word exists in the grid by following adjacent cells (horizontally or vertically). Each cell may be used at most once per path.

Approach

This is a grid-based backtracking problem. For each cell matching the first character, start a DFS that tries to match subsequent characters through adjacent cells. Mark cells as visited to prevent reuse, and unmark on backtrack.

Key Insights

• Start DFS from every cell that matches word[0]
• At each step, explore 4 neighbors (up, down, left, right)
• Prune immediately if the current cell does not match the expected character
• Temporarily modify the grid (e.g., replace with '#') instead of maintaining a separate visited matrix for better cache performance

Implementation

Complexity: Time O(M × N × 4^L) where L is word length. Space O(L) for recursion stack.

Problem 3: Combination Sum

Statement: Given an array of distinct positive integers candidates and a target sum, find all unique combinations where the candidates sum to target. The same number may be used unlimited times.

Approach

Backtrack with a running sum. At each level, try including the current candidate (allow reuse by not advancing the index) or skip to the next candidate. Prune when the remaining target becomes negative.

Key Insight

Allowing repetition means we recurse with the *same* index (not i+1). To avoid duplicates like [2,3] and [3,2], we only consider candidates from the current index onward.

Implementation

Variation — Combination Sum II (each number used at most once): Change backtrack(i, ...) to backtrack(i+1, ...) and skip duplicates with if i > start and candidates[i] == candidates[i-1]: continue.

Complexity: Time O(N^(T/M)) where T=target, M=minimum candidate. Space O(T/M) for recursion depth.

Problem 4: Palindrome Partitioning

Statement: Given a string s, partition it such that every substring in the partition is a palindrome. Return all such partitions.

Approach

At each position, try every possible prefix that forms a palindrome. If it is a palindrome, add it to the current partition and recurse on the remaining suffix. When the remaining string is empty, we have found a valid partitioning.

Dry Run

Implementation

Optimization with DP Precomputation

Precompute a palindrome lookup table to avoid repeated O(N) palindrome checks:

Complexity: Time O(N × 2^N) in worst case (e.g., "aaa...a"). Space O(N²) for DP table.

Summary Table

All four problems follow the same meta-pattern: choose → validate → recurse → undo. The differences lie in what constitutes a "choice" and what constraint enables pruning.