Backtracking
1. What Is Backtracking?¶
Definition:
Backtracking is a general algorithmic technique that incrementally builds candidates for the solutions and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly lead to a valid solution.
How It Works:
- Recursive Exploration: The algorithm makes a series of choices, exploring deeper until it either finds a valid solution or reaches a dead end.
- Undoing Decisions: When a path doesn’t lead to a valid solution, the algorithm backtracks by undoing the last choice and trying a different option.
- Pruning: Often, conditions (or “pruning”) are applied to cut off branches that won’t yield a solution, greatly improving efficiency.
2. Backtracking Template & Techniques¶
A. Basic Recursive Template¶
A basic backtracking template in pseudocode looks like:
def backtrack(path, options):
# Base case: if the current path is a complete solution, record it
if is_solution(path):
add_to_result(path)
return
for option in options:
# make a choice
if is_valid(option, path):
path.append(option)
# Recurse with the updated path
backtrack(path, updated_options(options, option))
# Undo the choice (backtrack)
path.pop()
B. Key Components of the Template¶
-
Base Case:
Determine when a solution has been found (e.g., path length equals target length, or when a sum is reached). -
Iteration Over Options:
For each decision point, iterate over all possible choices. -
Validation Check:
Check if the current option maintains the validity of the candidate solution. This may involve:- Checking if a number is already used.
- Verifying that a sum doesn’t exceed a target.
- Ensuring that the current configuration does not violate problem constraints.
- Recursion & Backtracking:
After making a valid choice, recursively explore further. If that path fails, undo the choice (backtracking).
-
Pruning:
Incorporate early exit conditions (pruning) to avoid exploring obviously invalid paths.
3. Common Backtracking Problem Types (题型) and Their Real-World Applications¶
3.1. Permutations¶
Description:
Generate all possible orders of a list of numbers or characters.
Typical LeetCode Problems:
Real-World Applications:
- Scheduling Tasks: Arranging tasks in every possible order to find the optimal sequence.
- Route Planning: Enumerating all possible routes for delivery or travel.
Example Code Snippet:
def permute(nums):
res = []
def backtrack(path, used):
if len(path) == len(nums):
res.append(path.copy())
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
path.append(nums[i])
backtrack(path, used)
path.pop()
used[i] = False
backtrack([], [False]*len(nums))
return res
3.2. Subsets (Power Set)¶
Description:
Generate all possible subsets of a set.
Typical LeetCode Problems:
Real-World Applications:
- Feature Selection: In machine learning, testing different combinations of features.
- Resource Allocation: Evaluating all combinations of resource assignments in a project.
Example Code Snippet:
def subsets(nums):
res = []
def backtrack(start, path):
res.append(path.copy())
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i+1, path)
path.pop()
backtrack(0, [])
return res
3.3. Combination Sum / Sum Problems¶
Description:
Find all unique combinations in an array where the chosen numbers sum up to a target.
Typical LeetCode Problems:
Real-World Applications:
- Budgeting: Finding combinations of expenses that meet a target budget.
- Coin Change: Determining all ways to give change for a particular amount.
Example Code Snippet:
def combinationSum(candidates, target):
res = []
def backtrack(start, path, current_sum):
if current_sum == target:
res.append(path.copy())
return
if current_sum > target:
return
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(i, path, current_sum + candidates[i])
path.pop()
backtrack(0, [], 0)
return res
3.4. Palindrome Partitioning¶
Description:
Partition a string such that every substring is a palindrome.
Typical LeetCode Problems:
Real-World Applications:
- Text Segmentation: Breaking text into meaningful units (e.g., in natural language processing).
- DNA Sequence Analysis: Identifying palindromic sequences in genetic data.
Example Code Snippet:
def partition(s):
res = []
def is_palindrome(sub):
return sub == sub[::-1]
def backtrack(start, path):
if start == len(s):
res.append(path.copy())
return
for end in range(start+1, len(s)+1):
substring = s[start:end]
if is_palindrome(substring):
path.append(substring)
backtrack(end, path)
path.pop()
backtrack(0, [])
return res
3.5. Constraint Satisfaction Problems (e.g., N-Queens, Sudoku)¶
Description:
Place items on a board such that they meet specific constraints (e.g., no two queens attack each other).
Typical LeetCode Problems:
Real-World Applications:
- Scheduling: Allocating time slots to events without conflicts.
- Resource Distribution: Assigning resources while ensuring no conflicts (like in wireless channel allocation).
Example Code Snippet (N-Queens):
def solveNQueens(n):
res = []
board = [["."] * n for _ in range(n)]
def is_valid(row, col):
for i in range(row):
if board[i][col] == "Q":
return False
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i][j] == "Q":
return False
i, j = i - 1, j - 1
i, j = row - 1, col + 1
while i >= 0 and j < n:
if board[i][j] == "Q":
return False
i, j = i - 1, j + 1
return True
def backtrack(row):
if row == n:
res.append(["".join(r) for r in board])
return
for col in range(n):
if is_valid(row, col):
board[row][col] = "Q"
backtrack(row + 1)
board[row][col] = "."
backtrack(0)
return res
3.6. Grid-Based Searches (e.g., Word Search, Maze Solving)¶
Description:
Search paths in a grid where you follow specific rules (e.g., adjacent moves).
Typical LeetCode Problems:
Real-World Applications:
- Path Finding: Navigating a robot through a maze.
- Game Development: Finding paths or solving puzzles within grid-based games.
Example Code Snippet:
def exist(board, word):
rows, cols = len(board), len(board[0])
def backtrack(r, c, idx):
if idx == len(word):
return True
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[idx]:
return False
temp = board[r][c]
board[r][c] = '#' # mark as visited
# explore neighbors
found = (backtrack(r+1, c, idx+1) or
backtrack(r-1, c, idx+1) or
backtrack(r, c+1, idx+1) or
backtrack(r, c-1, idx+1))
board[r][c] = temp # backtrack
return found
for i in range(rows):
for j in range(cols):
if board[i][j] == word[0] and backtrack(i, j, 0):
return True
return False
4. Tips and Optimizations for Backtracking¶
-
Pruning Early:
Apply checks before diving deeper (e.g., if current sum exceeds target, stop recursion). -
Avoiding Duplicates:
Use sorting or sets to avoid generating duplicate solutions, especially in problems like subsets and permutations. -
Memory Management:
Use in-place modifications (with careful backtracking) to save space. -
Iterative Deepening:
For some problems, iterative deepening (gradually increasing the depth limit) can optimize search.
5. Real-Life Coding Applications¶
Backtracking isn’t just for puzzles—it’s widely used in:
-
Scheduling and Planning:
Finding optimal schedules or resource allocation (e.g., meeting scheduling, production planning). -
Configuration Management:
Automating configuration setups where many combinations of settings need to be tested. -
Decision Making in Games:
Generating possible moves and strategies in games (e.g., chess move exploration). -
Bioinformatics:
DNA sequencing and protein folding problems that require exploring many possible combinations. -
Artificial Intelligence:
Solving constraint satisfaction problems like pathfinding and puzzle solving.
Summary¶
- Backtracking is a method to explore all possible solutions by making choices, exploring further, and backtracking upon reaching dead ends.
- Templates typically involve recursive functions with a base case, a loop over candidate choices, and a backtracking step to undo choices.
- Problem Types include permutations, subsets, combination sums, palindrome partitioning, constraint problems (like N-Queens), and grid-based searches—all of which have practical real-life applications in scheduling, planning, resource allocation, and more.
This guide should serve as both a reference for tackling LeetCode problems and an insight into how these strategies translate into solving complex, real-world coding challenges.