Chapter 7: Backtracking
Master backtracking algorithms for permutations, combinations, and constraint satisfaction problems. Learn when and where to use backtracking.
1. Backtracking Fundamentals
📌 When and Where to Use
- Constraint satisfaction: Problems with constraints (N-Queens, Sudoku)
- Combinatorial problems: Permutations, combinations, subsets
- Search problems: Finding all solutions or one solution
- Real-world example: Scheduling with constraints, puzzle solving, generating all possible configurations, or resource allocation with rules
Backtracking Template
def backtrack(choices, path, result):
"""
General backtracking template.
Args:
choices: Available choices at current step
path: Current partial solution
result: List to store all valid solutions
"""
# Step 1: Base case - solution found
if is_solution(path):
result.append(path.copy()) # Save a copy
return
# Step 2: Try each choice
for choice in choices:
# Step 3: Check if choice is valid
if is_valid(choice, path):
# Step 4: Make choice (add to path)
path.append(choice)
# Step 5: Recurse with updated path
backtrack(updated_choices, path, result)
# Step 6: Backtrack (undo choice)
path.pop()Step-by-Step Explanation:
Step 1 - Base Case: If current path is a complete solution, save it.
Step 2 - Try Choices: Iterate through all possible choices.
Step 3 - Validate: Check if choice is valid given current path.
Step 4 - Make Choice: Add choice to path.
Step 5 - Recurse: Explore further with this choice.
Step 6 - Backtrack: Remove choice (undo) to try other possibilities.
2. Permutations
Example: All Permutations
def permute(nums):
"""
Generate all permutations of array.
Args:
nums: List of distinct integers
Returns:
List of all permutations
"""
result = []
def backtrack(path, remaining):
# Step 1: Base case - all elements used
if len(remaining) == 0:
result.append(path.copy())
return
# Step 2: Try each remaining element
for i in range(len(remaining)):
# Step 3: Make choice
# Add current element to path
path.append(remaining[i])
# Step 4: Update remaining (remove chosen element)
new_remaining = remaining[:i] + remaining[i + 1:]
# Step 5: Recurse
backtrack(path, new_remaining)
# Step 6: Backtrack
path.pop()
# Step 7: Start backtracking
backtrack([], nums)
return resultStep-by-Step Code Walkthrough:
Step 1 - Base Case: If no elements remaining, we have a complete permutation.
Step 2 - Try Each: For each remaining element, try adding it to path.
Step 3 - Make Choice: Add element to current path.
Step 4 - Update Remaining: Remove chosen element from remaining list.
Step 5 - Recurse: Continue building permutation with updated path and remaining.
Step 6 - Backtrack: Remove element from path to try other choices.
Step 7 - Start: Begin with empty path and all elements as remaining.
Example:
nums = [1, 2, 3]
Result: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
3. Combinations
Example: All Combinations of Size K
def combine(n, k):
"""
Generate all combinations of k numbers from 1 to n.
Args:
n: Range [1, n]
k: Size of combination
Returns:
List of all combinations
"""
result = []
def backtrack(start, path):
# Step 1: Base case - combination of size k found
if len(path) == k:
result.append(path.copy())
return
# Step 2: Try each number from start to n
for i in range(start, n + 1):
# Step 3: Make choice
path.append(i)
# Step 4: Recurse with next start (avoid duplicates)
# Start from i+1 to ensure increasing order
backtrack(i + 1, path)
# Step 5: Backtrack
path.pop()
# Step 6: Start from 1
backtrack(1, [])
return resultStep-by-Step Code Walkthrough:
Step 1 - Base Case: If path has k elements, we have a valid combination.
Step 2 - Try Numbers: Try each number from start to n.
Step 3 - Make Choice: Add number to path.
Step 4 - Recurse: Continue with next start = i+1 (ensures increasing order, avoids duplicates).
Step 5 - Backtrack: Remove number to try other choices.
Step 6 - Start: Begin from number 1.
Example:
n = 4, k = 2
Result: [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
4. N-Queens Problem
📌 When and Where to Use
- Constraint satisfaction: Placing items with constraints
- Real-world example: Scheduling with conflicts, resource allocation with restrictions, or layout problems
Example: N-Queens Solution
def solve_n_queens(n):
"""
Place n queens on n×n board so no two attack each other.
Args:
n: Size of board and number of queens
Returns:
List of all solutions (each solution is list of queen positions)
"""
result = []
def is_safe(row, col, board):
# Step 1: Check column
for i in range(row):
if board[i] == col:
return False
# Step 2: Check diagonal (top-left to bottom-right)
for i in range(row):
if board[i] - i == col - row:
return False
# Step 3: Check anti-diagonal (top-right to bottom-left)
for i in range(row):
if board[i] + i == col + row:
return False
return True
def backtrack(row, board):
# Step 4: Base case - all queens placed
if row == n:
result.append(board.copy())
return
# Step 5: Try each column in current row
for col in range(n):
# Step 6: Check if safe to place queen
if is_safe(row, col, board):
# Step 7: Place queen
board[row] = col
# Step 8: Recurse to next row
backtrack(row + 1, board)
# Step 9: Backtrack (board[row] will be overwritten)
# No explicit undo needed as we overwrite
# Step 10: Start from row 0
backtrack(0, [-1] * n)
return resultStep-by-Step Code Walkthrough:
is_safe function:
- Step 1: Check if any previous queen is in same column
- Step 2: Check diagonal (same difference: row-col)
- Step 3: Check anti-diagonal (same sum: row+col)
backtrack function:
- Step 4: If all rows processed, save solution
- Step 5: Try each column in current row
- Step 6: Check if placing queen here is safe
- Step 7: Place queen (store column in board[row])
- Step 8: Recurse to next row
- Step 9: Backtrack (will be overwritten in next iteration)
Step 10: Start from row 0 with empty board.
5. Subsets
Example: All Subsets
def subsets(nums):
"""
Generate all subsets of array.
Args:
nums: List of integers
Returns:
List of all subsets
"""
result = []
def backtrack(start, path):
# Step 1: Add current path (subset) to result
# Add at every step, not just at base case
result.append(path.copy())
# Step 2: Try each element from start to end
for i in range(start, len(nums)):
# Step 3: Make choice
path.append(nums[i])
# Step 4: Recurse with next start
backtrack(i + 1, path)
# Step 5: Backtrack
path.pop()
# Step 6: Start from index 0
backtrack(0, [])
return resultStep-by-Step Code Walkthrough:
Step 1 - Add Subset: Add current path to result (every path is a valid subset).
Step 2 - Try Elements: Try each element from start position.
Step 3 - Make Choice: Include element in subset.
Step 4 - Recurse: Continue with next start (i+1) to avoid duplicates.
Step 5 - Backtrack: Remove element to try subsets without it.
Step 6 - Start: Begin from index 0.
Example:
nums = [1, 2, 3]
Result: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
📚 Chapter Summary
- Template: Make choice → Recurse → Backtrack (undo choice)
- Permutations: Order matters, use all elements
- Combinations: Order doesn't matter, use subset
- Subsets: All possible subsets (power set)
- Constraint Problems: Add validation (is_safe) before making choice
Key Takeaway: Backtracking explores all possibilities by trying choices, recursing, and undoing choices. Pruning (early termination) is crucial for efficiency.