Backtracking

Backtracking Pattern

Backtracking is an algorithmic technique that considers searching every possible combination in a systematic way. It builds candidates incrementally and abandons candidates (“backtracks”) when they cannot lead to a valid solution. Unlike brute force, it intelligently prunes the search space.

When to use Backtracking?

• Combinatorial Problems

  • Generating all possible permutations
  • Finding all possible combinations
  • Subset sum problems
  • String combinations

• Constraint Satisfaction

  • Sudoku solver
  • N-Queens placement
  • Map coloring
  • Crossword puzzle solving

• Path Finding

  • Maze solving
  • Knight’s tour
  • Hamiltonian paths
  • Robot path planning

• Game Problems

  • Chess endgames
  • Tic-tac-toe solver
  • Word search
  • Game tree exploration

How it Works

1. Basic Concept

   • Incremental Construction

     • Build solution step by step
     • Make choices at each step
     • Track current state
     • Maintain solution constraints

   • State Space Tree

     • Represent all possibilities
     • Organize choices hierarchically
     • Prune invalid branches early
     • Track visited states

   • Validation

     • Check constraints at each step
     • Verify partial solutions
     • Early termination on invalid paths
     • Optimization opportunities

   • Backtracking Process

     • Save state before exploring
     • Restore state after exploration
     • Handle multiple choices
     • Implement efficient rollback

Basic Template

def backtrack(input, path, result):
    if isComplete(path):
        result.append(path.copy())
        return
    
    for candidate in getCandidates(input, path):
        if isValid(candidate, path):
            # Make choice
            path.append(candidate)
            
            # Explore further
            backtrack(input, path, result)
            
            # Undo choice
            path.pop()

Common Variations

1. N-Queens Problem

def solveNQueens(n):
    def isValid(board, row, col):
        # Check column
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        
        # Check diagonal
        for i, j in zip(range(row-1, -1, -1),
                       range(col-1, -1, -1)):
            if board[i][j] == 'Q':
                return False
        
        # Check other diagonal
        for i, j in zip(range(row-1, -1, -1),
                       range(col+1, n)):
            if board[i][j] == 'Q':
                return False
        
        return True
    
    def backtrack(row, board):
        if row == n:
            result.append([''.join(row) for row in board])
            return
        
        for col in range(n):
            if isValid(board, row, col):
                board[row][col] = 'Q'
                backtrack(row + 1, board)
                board[row][col] = '.'
    
    result = []
    board = [['.' for _ in range(n)] for _ in range(n)]
    backtrack(0, board)
    return result

2. Subset Generation

def subsets(nums):
    def backtrack(start, path):
        result.append(path[:])
        
        for i in range(start, len(nums)):
            # Make choice
            path.append(nums[i])
            
            # Explore
            backtrack(i + 1, path)
            
            # Undo choice
            path.pop()
    
    result = []
    backtrack(0, [])
    return result

Edge Cases to Consider

1. Empty input
2. Single element
3. Duplicate elements
4. No solution exists
5. Multiple solutions
6. Maximum recursion depth
7. Large input size

Tips

1. Identify base cases clearly
2. Optimize pruning conditions
3. Handle state properly
4. Consider solution uniqueness
5. Watch for stack overflow

Time & Space Complexity

• Often exponential time O(b^d)
• Space complexity O(d) for recursion
• b = branching factor
• d = maximum depth
• Consider pruning effectiveness

Implementation Patterns

1. Choice-Based Backtracking

def permutations(nums):
    def backtrack(used, path):
        if len(path) == len(nums):
            result.append(path[:])
            return
            
        for i in range(len(nums)):
            # Skip used elements
            if used[i]:
                continue
                
            # Make choice
            used[i] = True
            path.append(nums[i])
            
            # Explore
            backtrack(used, path)
            
            # Undo choice
            used[i] = False
            path.pop()
    
    result = []
    backtrack([False] * len(nums), [])
    return result

2. Position-Based Backtracking

def combinationSum(candidates, target):
    def backtrack(start, target, path):
        if target == 0:
            result.append(path[:])
            return
        if target < 0:
            return
            
        for i in range(start, len(candidates)):
            # Make choice
            path.append(candidates[i])
            
            # Explore (can reuse same element)
            backtrack(i, target - candidates[i], path)
            
            # Undo choice
            path.pop()
    
    result = []
    candidates.sort()  # Optimization
    backtrack(0, target, [])
    return result

3. Matrix Backtracking

def solveSudoku(board):
    def isValid(num, pos):
        # Check row
        for x in range(9):
            if board[pos[0]][x] == num:
                return False
                
        # Check column
        for x in range(9):
            if board[x][pos[1]] == num:
                return False
        
        # Check box
        box_x = pos[1] // 3
        box_y = pos[0] // 3
        for i in range(box_y * 3, box_y * 3 + 3):
            for j in range(box_x * 3, box_x * 3 + 3):
                if board[i][j] == num:
                    return False
        return True

    def solve():
        for i in range(9):
            for j in range(9):
                if board[i][j] == ".":
                    for num in map(str, range(1, 10)):
                        if isValid(num, (i, j)):
                            board[i][j] = num
                            if solve():
                                return True
                            board[i][j] = "."
                    return False
        return True
    
    solve()

4. String Backtracking

def letterCombinations(digits):
    if not digits:
        return []
        
    phone_map = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    
    def backtrack(index, path):
        if len(path) == len(digits):
            result.append(''.join(path))
            return
            
        for letter in phone_map[digits[index]]:
            path.append(letter)
            backtrack(index + 1, path)
            path.pop()
    
    result = []
    backtrack(0, [])
    return result

Optimization Techniques

1. State Pruning

   • Track invalid states
   • Skip redundant paths
   • Use visited sets
   • Maintain constraints

2. Sort-Based Optimization

   • Pre-sort input
   • Skip duplicates
   • Early termination
   • Binary search choices

3. Memory Optimization

   • Iterative deepening
   • Bit manipulation
   • State compression
   • Path optimization

Advanced Interview Problems

1. Expression Generator

def addOperators(num: str, target: int) -> list[str]:
    def backtrack(index: int, prev_operand: int, current_operand: int, value: int, expression: list[str]):
        # Base case: reached end of num string
        if index == len(num):
            if value == target and current_operand == 0:
                result.append(''.join(expression[1:]))
            return

        # Current operand can be multi-digit
        current_operand = current_operand * 10 + int(num[index])
        str_op = str(current_operand)
        
        # Case 1: Continue building current operand
        if current_operand > 0:
            backtrack(index + 1, prev_operand, current_operand, value, expression)

        # Case 2: Addition
        expression.append('+')
        expression.append(str_op)
        backtrack(index + 1, current_operand, 0, value + current_operand, expression)
        expression.pop()
        expression.pop()

        if expression:  # Can't subtract/multiply without previous operand
            # Case 3: Subtraction
            expression.append('-')
            expression.append(str_op)
            backtrack(index + 1, -current_operand, 0, value - current_operand, expression)
            expression.pop()
            expression.pop()

            # Case 4: Multiplication
            expression.append('*')
            expression.append(str_op)
            backtrack(index + 1, 
                     current_operand * prev_operand, 
                     0,
                     value - prev_operand + (prev_operand * current_operand),
                     expression)
            expression.pop()
            expression.pop()

    result = []
    if not num:
        return result
    backtrack(0, 0, 0, 0, [])
    return result

2. Word Pattern Matcher

def wordPatternMatch(pattern: str, s: str) -> bool:
    def backtrack(pattern_idx: int, str_idx: int, pattern_map: dict, used_words: set) -> bool:
        # Base case: both pattern and string are exhausted
        if pattern_idx == len(pattern) and str_idx == len(s):
            return True
        # If either is exhausted but not both
        if pattern_idx == len(pattern) or str_idx == len(s):
            return False

        char = pattern[pattern_idx]
        
        # If pattern char already mapped
        if char in pattern_map:
            word = pattern_map[char]
            if not s.startswith(word, str_idx):
                return False
            return backtrack(pattern_idx + 1, str_idx + len(word), pattern_map, used_words)
        
        # Try all possible words for current pattern char
        for end in range(str_idx + 1, len(s) + 1):
            word = s[str_idx:end]
            if word in used_words:
                continue
                
            pattern_map[char] = word
            used_words.add(word)
            
            if backtrack(pattern_idx + 1, end, pattern_map, used_words):
                return True
                
            pattern_map.pop(char)
            used_words.remove(word)
            
        return False

    return backtrack(0, 0, {}, set())

3. Remove Invalid Parentheses

def removeInvalidParentheses(s: str) -> list[str]:
    def isValid(s: str) -> bool:
        count = 0
        for char in s:
            if char == '(':
                count += 1
            elif char == ')':
                count -= 1
            if count < 0:
                return False
        return count == 0

    def backtrack(s: str, start: int, left_count: int, right_count: int) -> None:
        if left_count == 0 and right_count == 0:
            if isValid(s):
                result.add(s)
            return

        for i in range(start, len(s)):
            # Skip duplicates
            if i > start and s[i] == s[i-1]:
                continue

            # Try removing current character
            if right_count > 0 and s[i] == ')':
                backtrack(s[:i] + s[i+1:], i, left_count, right_count - 1)
            if left_count > 0 and s[i] == '(':
                backtrack(s[:i] + s[i+1:], i, left_count - 1, right_count)

    # Count invalid parentheses
    left = right = 0
    for char in s:
        if char == '(':
            left += 1
        elif char == ')':
            if left == 0:
                right += 1
            else:
                left -= 1

    result = set()
    backtrack(s, 0, left, right)
    return list(result) if result else [""]

Interview Tips & Tricks

1. Pattern Recognition

   • Look for combinatorial nature
   • Identify constraint patterns
   • Consider state representation
   • Analyze pruning opportunities

2. Optimization Strategies

   • Use memoization when possible
   • Implement early pruning
   • Consider iterative approaches
   • Optimize state transitions

3. Common Pitfalls

   • Stack overflow in deep recursion
   • Inefficient state copying
   • Missing edge cases
   • Incorrect backtracking

4. Testing Approach

   • Start with small inputs
   • Test edge cases first
   • Verify state restoration
   • Check memory usage

Visualization Techniques

1. State Space Tree Visualization

class StateNode:
    def __init__(self, state, parent=None):
        self.state = state
        self.parent = parent
        self.children = []
        self.pruned = False
        
    def add_child(self, child_state):
        child = StateNode(child_state, self)
        self.children.append(child)
        return child
        
    def visualize(self, level=0):
        prefix = "  " * level
        status = "❌" if self.pruned else "✅"
        print(f"{prefix}{status} {self.state}")
        for child in self.children:
            child.visualize(level + 1)

def visualizeNQueens(n: int):
    root = StateNode("root")
    
    def place_queen(node, row):
        if row == n:
            return True
            
        board = node.state if node.state != "root" else [['.'] * n for _ in range(n)]
        
        for col in range(n):
            if is_safe(board, row, col):
                new_board = [row[:] for row in board]
                new_board[row][col] = 'Q'
                child = node.add_child(new_board)
                
                if place_queen(child, row + 1):
                    return True
                child.pruned = True
                
        return False
    
    place_queen(root, 0)
    root.visualize()

2. Decision Tree Visualization

def visualizePermutations(nums):
    def format_state(used, current):
        available = [n for i, n in enumerate(nums) if not used[i]]
        return f"Current: {current}, Available: {available}"
    
    def backtrack(used, path, level=0):
        prefix = "│  " * level
        state = format_state(used, path)
        print(f"{prefix}├─ {state}")
        
        if len(path) == len(nums):
            print(f"{prefix}│  └─ Solution: {path}")
            return
            
        for i in range(len(nums)):
            if used[i]:
                continue
                
            used[i] = True
            path.append(nums[i])
            backtrack(used, path, level + 1)
            path.pop()
            used[i] = False
    
    print("Permutation Decision Tree:")
    backtrack([False] * len(nums), [])

More Advanced Interview Problems

1. Palindrome Decomposition

def palindromeDecomposition(s: str) -> list[list[str]]:
    def isPalindrome(start: int, end: int) -> bool:
        while start < end:
            if s[start] != s[end]:
                return False
            start += 1
            end -= 1
        return True
    
    def backtrack(start: int, path: list[str]) -> None:
        if start >= len(s):
            result.append(path[:])
            return
        
        # Try all possible palindrome prefixes
        for end in range(start, len(s)):
            if isPalindrome(start, end):
                path.append(s[start:end + 1])
                backtrack(end + 1, path)
                path.pop()
    
    result = []
    backtrack(0, [])
    return result

2. Word Break with All Solutions

def wordBreakAll(s: str, wordDict: set[str]) -> list[str]:
    def backtrack(start: int, memo: dict) -> list[str]:
        if start in memo:
            return memo[start]
            
        if start == len(s):
            return [""]
            
        results = []
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in wordDict:
                subResults = backtrack(end, memo)
                for sub in subResults:
                    results.append((word + " " + sub).strip())
                    
        memo[start] = results
        return results
    
    return backtrack(0, {})

3. Generate All Valid IP Addresses

def restoreIpAddresses(s: str) -> list[str]:
    def isValidSegment(segment: str) -> bool:
        if not segment or len(segment) > 3 or \
           (len(segment) > 1 and segment[0] == '0'):
            return False
        return 0 <= int(segment) <= 255
    
    def backtrack(start: int, dots: int, current: list[str]) -> None:
        if dots == 4 and start == len(s):
            result.append('.'.join(current))
            return
            
        if dots > 4:
            return
            
        for i in range(1, 4):
            if start + i <= len(s):
                segment = s[start:start + i]
                if isValidSegment(segment):
                    current.append(segment)
                    backtrack(start + i, dots + 1, current)
                    current.pop()
    
    result = []
    backtrack(0, 0, [])
    return result

Real-World Applications

1. Circuit Board Layout

def circuitBoardPlacement(board: list[list[int]], components: list[tuple]) -> bool:
    def canPlace(pos: tuple, size: tuple) -> bool:
        row, col = pos
        height, width = size
        if row + height > len(board) or col + width > len(board[0]):
            return False
            
        return all(board[r][c] == 0 
                  for r in range(row, row + height)
                  for c in range(col, col + width))
    
    def place(pos: tuple, size: tuple, id: int) -> None:
        row, col = pos
        height, width = size
        for r in range(row, row + height):
            for c in range(col, col + width):
                board[r][c] = id
    
    def remove(pos: tuple, size: tuple) -> None:
        row, col = pos
        height, width = size
        for r in range(row, row + height):
            for c in range(col, col + width):
                board[r][c] = 0
    
    def backtrack(component_idx: int) -> bool:
        if component_idx == len(components):
            return True
            
        size = components[component_idx]
        for row in range(len(board)):
            for col in range(len(board[0])):
                if canPlace((row, col), size):
                    place((row, col), size, component_idx + 1)
                    if backtrack(component_idx + 1):
                        return True
                    remove((row, col), size)
        return False
    
    return backtrack(0)