本文目录导读：
我来为您介绍几个Python回溯算法的经典案例,从简单到复杂逐步深入。
全排列问题（基础案例）
def permute(nums):
"""
生成所有可能的排列
时间复杂度：O(n!)
"""
def backtrack(path, used):
# 找到一组完整排列
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if not used[i]: # 当前数字未使用
# 做选择
used[i] = True
path.append(nums[i])
# 递归
backtrack(path, used)
# 撤销选择
path.pop()
used[i] = False
result = []
backtrack([], [False] * len(nums))
return result
# 测试
print(permute([1, 2, 3]))
# 输出: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
N皇后问题（经典回溯）
class NQueens:
"""
N皇后问题：在N×N棋盘上放置N个皇后，使其不能互相攻击
"""
def solveNQueens(self, n):
def is_valid(board, 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 -= 1
j -= 1
# 检查右上对角线
i, j = row - 1, col + 1
while i >= 0 and j < n:
if board[i][j] == 'Q':
return False
i -= 1
j += 1
return True
def backtrack(board, row):
# 找到解
if row == n:
result.append([''.join(row) for row in board])
return
for col in range(n):
if is_valid(board, row, col):
# 放置皇后
board[row][col] = 'Q'
# 递归下一行
backtrack(board, row + 1)
# 撤销操作
board[row][col] = '.'
# 初始化棋盘
board = [['.' for _ in range(n)] for _ in range(n)]
result = []
backtrack(board, 0)
return result
# 测试4皇后
queens = NQueens()
solutions = queens.solveNQueens(4)
print(f"4皇后共有 {len(solutions)} 种解法：")
for sol in solutions:
print("\n".join(sol))
print()
数独求解器
class SudokuSolver:
"""
解数独问题：填充9x9数独网格
"""
def solveSudoku(self, board):
def is_valid(board, row, col, num):
# 检查行
if num in board[row]:
return False
# 检查列
for r in range(9):
if board[r][col] == num:
return False
# 检查3x3子网格
start_row, start_col = 3 * (row // 3), 3 * (col // 3)
for r in range(start_row, start_row + 3):
for c in range(start_col, start_col + 3):
if board[r][c] == num:
return False
return True
def find_empty(board):
"""找到第一个空单元格"""
for r in range(9):
for c in range(9):
if board[r][c] == '.':
return r, c
return None, None
def backtrack(board):
# 找到空位
row, col = find_empty(board)
# 没有空位，数独已填满
if row is None:
return True
# 尝试1-9
for num in range(1, 10):
num_str = str(num)
if is_valid(board, row, col, num_str):
# 填入数字
board[row][col] = num_str
# 递归
if backtrack(board):
return True
# 撤销
board[row][col] = '.'
return False
backtrack(board)
return board
# 测试
sudoku = [
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
solver = SudokuSolver()
solution = solver.solveSudoku(sudoku)
print("解出的数独：")
for row in solution:
print(" ".join(row))
组合总和问题
def combinationSum(candidates, target):
"""
找出所有和为target的组合（数字可以重复使用）
时间复杂度：O(2^n)
"""
def backtrack(remain, start, path):
"""
remain: 剩余需要凑的目标和
start: 从哪个索引开始（避免重复组合）
path: 当前路径
"""
# 找到有效组合
if remain == 0:
result.append(path[:])
return
# 超过目标值，剪枝
if remain < 0:
return
for i in range(start, len(candidates)):
# 选择当前数字
path.append(candidates[i])
# 递归（注意：允许重复使用，所以i不变）
backtrack(remain - candidates[i], i, path)
# 撤销选择
path.pop()
result = []
candidates.sort() # 排序方便剪枝
backtrack(target, 0, [])
return result
# 测试
candidates = [2, 3, 6, 7]
target = 7
print(f"组合总和 {target}: {combinationSum(candidates, target)}")
# 输出: [[2, 2, 3], [7]]
单词搜索（矩阵中的路径）
def exist(board, word):
"""
在二维网格中查找单词
时间复杂度：O(M*N*4^L)，L为单词长度
"""
def backtrack(i, j, index):
# 找到完整单词
if index == len(word):
return True
# 边界检查
if (i < 0 or i >= rows or j < 0 or j >= cols
or visited[i][j] or board[i][j] != word[index]):
return False
# 标记访问
visited[i][j] = True
# 四个方向探索
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for di, dj in directions:
if backtrack(i + di, j + dj, index + 1):
return True
# 撤销标记
visited[i][j] = False
return False
rows, cols = len(board), len(board[0])
visited = [[False for _ in range(cols)] for _ in range(rows)]
# 从每个位置开始尝试
for i in range(rows):
for j in range(cols):
if board[i][j] == word[0]:
if backtrack(i, j, 0):
return True
return False
# 测试
board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
words = ["ABCCED", "SEE", "ABCB"]
for w in words:
print(f"是否存在 '{w}': {exist(board, w)}")
回溯算法性能优化技巧
class BacktrackOptimization:
"""
回溯算法优化示例：使用剪枝和记忆化搜索
问题：分割回文串
"""
def partition(self, s):
"""
分割字符串为所有可能的回文子串组合
"""
def is_palindrome(s, left, right):
"""判断子串是否为回文"""
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
def backtrack(start, path):
# 到达字符串末尾
if start == len(s):
result.append(path[:])
return
# 优化1：使用缓存避免重复计算回文判断
for end in range(start, len(s)):
# 优化2：提前剪枝
if is_palindrome(s, start, end):
path.append(s[start:end+1])
backtrack(end + 1, path)
path.pop()
result = []
backtrack(0, [])
return result
def solveWithMemoization(self):
"""
使用记忆化搜索优化
问题：不同路径III
"""
def uniquePathsIII(grid):
def dfs(i, j, remaining):
# 越界或障碍物
if (i < 0 or i >= m or j < 0 or j >= n
or grid[i][j] == -1 or visited[i][j]):
return 0
# 到达终点
if grid[i][j] == 2:
return 1 if remaining == 0 else 0
# 记忆化搜索
key = (i, j, remaining)
if key in memo:
return memo[key]
visited[i][j] = True
total = 0
for di, dj in [(0,1), (1,0), (0,-1), (-1,0)]:
total += dfs(i + di, j + dj, remaining - 1)
visited[i][j] = False
memo[key] = total
return total
m, n = len(grid), len(grid[0])
start = end = None
empty_count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
start = (i, j)
elif grid[i][j] == 2:
end = (i, j)
elif grid[i][j] == 0:
empty_count += 1
visited = [[False] * n for _ in range(m)]
memo = {}
return dfs(start[0], start[1], empty_count + 1) # +1 for start cell
# 测试
grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
print(f"不同路径III的解数: {uniquePathsIII(grid)}")
# 运行测试
opt = BacktrackOptimization()
print("回文串分割结果:", opt.partition("aab"))
opt.solveWithMemoization()
实用技巧总结
def backtrack_template():
"""
回溯算法通用模板
"""
def backtrack(状态参数):
# 终止条件
if 满足结束条件:
保存结果
return
for 选择 in 当前可选列表:
# 剪枝条件（可选）
if 不满足条件:
continue
# 做选择
更新状态
# 递归
backtrack(新状态)
# 撤销选择
恢复状态
result = []
backtrack(初始状态)
return result
# 使用字典理解回溯算法
backtrack_essence = {
"核心思想": "枚举所有可能的解，并在搜索过程中剪枝",
"三个要点": [
"路径：已经做出的选择",
"选择列表：当前可以做的选择",
"结束条件：到达决策树底层"
],
"优化方向": [
"剪枝：提前排除无效分支",
"排序：使相同元素相邻便于去重",
"记忆化：缓存子问题的解",
"位运算：优化状态表示和判断"
]
}
这些案例涵盖了回溯算法的主要应用场景,从简单的排列组合到复杂的约束满足问题，记住回溯算法的核心是"选择-探索-撤销"的循环，配合适当的剪枝可以大幅提升效率。
标签： 八皇后问题