回溯算法问题
1. 核心思想
回溯是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解不符合要求，就回退到上一步继续尝试。
2. 适用场景
- 排列组合问题
- 子集问题
- 棋盘问题（N皇后、数独）
- 路径搜索问题
- 分割问题
3. 通用模板
def backtrack(path, choices):
"""
path: 当前路径（已做的选择）
choices: 当前可选择的列表
"""
# 1. 终止条件
if 满足条件:
result.append(path[:]) # 注意要复制
return
# 2. 遍历所有选择
for choice in choices:
# 3. 做选择
path.append(choice)
# 4. 递归进入下一层
backtrack(path, new_choices)
# 5. 撤销选择（回溯）
path.pop()
4. 经典例题
例1: 全排列
def permute(nums):
"""
生成所有全排列
"""
result = []
def backtrack(path, used):
# 终止条件
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
# 剪枝：已使用过的元素不能再用
if used[i]:
continue
# 做选择
path.append(nums[i])
used[i] = True
# 递归
backtrack(path, used)
# 撤销选择
path.pop()
used[i] = False
backtrack([], [False] * len(nums))
return result
例2: 组合总和
def combinationSum(candidates, target):
"""
找出所有相加之和为target的组合（可重复使用）
"""
result = []
candidates.sort() # 排序便于剪枝
def backtrack(start, path, remain):
# 终止条件
if remain == 0:
result.append(path[:])
return
if remain < 0:
return
for i in range(start, len(candidates)):
# 剪枝：如果当前数字已经大于剩余值，后面的更大
if candidates[i] > remain:
break
# 做选择
path.append(candidates[i])
# 递归（注意：可以重复使用，所以从i开始）
backtrack(i, path, remain - candidates[i])
# 撤销选择
path.pop()
backtrack(0, [], target)
return result
例3: 子集
def subsets(nums):
"""
返回所有可能的子集
"""
result = []
def backtrack(start, path):
# 每个状态都是一个有效子集
result.append(path[:])
for i in range(start, len(nums)):
# 做选择
path.append(nums[i])
# 递归（从i+1开始，避免重复）
backtrack(i + 1, path)
# 撤销选择
path.pop()
backtrack(0, [])
return result
例4: N皇后
def solveNQueens(n):
"""
N皇后问题
"""
result = []
board = [['.'] * n for _ in range(n)]
def isValid(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(row):
# 终止条件
if row == n:
result.append([''.join(row) for row in board])
return
for col in range(n):
if not isValid(row, col):
continue
# 做选择
board[row][col] = 'Q'
# 递归下一行
backtrack(row + 1)
# 撤销选择
board[row][col] = '.'
backtrack(0)
return result
5. 优化技巧
剪枝策略
def combinationSum2(candidates, target):
"""
带去重的组合总和
"""
result = []
candidates.sort()
def backtrack(start, path, remain):
if remain == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
# 剪枝1: 数值过大
if candidates[i] > remain:
break
# 剪枝2: 去重（跳过同层重复元素）
if i > start and candidates[i] == candidates[i-1]:
continue
path.append(candidates[i])
backtrack(i + 1, path, remain - candidates[i])
path.pop()
backtrack(0, [], target)
return result
三、两种方法的对比
| 特性 | 单调栈 | 回溯 |
|---|---|---|
| 时间复杂度 | O(n) | 指数级（O(2^n)或O(n!)） |
| 空间复杂度 | O(n) | O(n)（递归深度） |
| 应用场景 | 寻找相邻关系 | 搜索所有解 |
| 核心思想 | 维护单调性 | 尝试+回退 |
| 是否需要回退 | 否 | 是 |
选择建议
- 用单调栈：当问题涉及找"下一个更大/小元素"或需要维护某种单调性
- 用回溯：当需要遍历所有可能的解空间，特别是排列、组合、子集问题
希望这份整理对你有帮助！如有具体问题，欢迎继续提问。