【算法】回溯法

回溯法（Backtracking）是一种通过试错来寻找问题解决方案的算法。其核心思想是逐步构建解，当发现当前路径无法得到有效解时，回溯到上一步，尝试其他可能性。它通常用于解决组合优化、排列组合、约束满足等问题（如八皇后、数独、全排列等）。

---

核心思想

1. 试错与回退：逐步尝试可能的解，遇到无效分支立即回退。
2. 剪枝（Pruning）：提前终止不可能产生有效解的路径，减少搜索空间。
3. 递归实现：通过递归函数处理每一步的选择，天然适合分步构建解。

---

算法框架

result = []  # 保存最终结果def backtrack(路径, 选择列表):if 满足结束条件:result.add(路径)returnfor 选择 in 选择列表:if 选择不合法（剪枝条件）:continue做选择（将选择加入路径）backtrack(新路径, 新选择列表)撤销选择（从路径中移除选择）

---

关键步骤

1. 路径：已做出的选择（如当前已选的元素）。
2. 选择列表：当前可选的元素。
3. 结束条件：路径满足问题约束，成为一个有效解。
4. 剪枝条件：提前跳过无效选择（如重复元素、违反约束等）。

---

经典问题示例

1. 全排列（Permutations）

问题：给定数组 [1,2,3]，返回所有可能的排列。
解法：

def permute(nums):res = []def backtrack(path, used):if len(path) == len(nums):res.append(path.copy())returnfor i in range(len(nums)):if not used[i]:used[i] = Truebacktrack(path + [nums[i]], used)used[i] = False  # 回溯backtrack([], [False]*len(nums))return res

2. 八皇后问题（N-Queens）

问题：在N×N棋盘放置N个皇后，使其互不攻击。
解法：

def solveNQueens(n):res = []def backtrack(board, row):if row == n:res.append([''.join(row) for row in board])returnfor col in range(n):if isValid(board, row, col):board[row][col] = 'Q'backtrack(board, row + 1)board[row][col] = '.'  # 回溯# 初始化棋盘并开始回溯board = [['.']*n for _ in range(n)]backtrack(board, 0)return res

---

优化策略

• 剪枝：根据问题特性提前排除无效路径（如组合问题中限制起始位置）。
• 记忆化：缓存已处理状态，避免重复计算（适用于重叠子问题）。
• 交换法：通过交换元素减少空间复杂度（如全排列问题）。

---

时间复杂度

• 通常为指数级，例如：
  • 全排列：O(n!)
  • 子集问题：O(2^n)
• 剪枝能显著降低实际运行时间。

---

适用场景

• 需要穷举所有可能解的问题。
• 问题可分解为多步决策，且每一步有有限选择。
• 约束条件明确，便于剪枝优化。

回溯法通过系统性的试探与回退，结合剪枝策略，能高效解决许多复杂的组合问题。

参考：

演算法學習筆記：回溯法（Backtracking）& 分支定界法（Branch and Bound）