简单回溯（自用）

一、回溯算法概述回溯算法Backtracking是一种通过探索所有可能候选解来求解问题的算法。如果某个候选解被证明不是可行解则回溯到上一步尝试其他候选解。核心思想深度优先搜索 剪枝优化适用场景组合问题如排列组合、子集分割问题如字符串分割、数独约束满足问题如N皇后、数独求解路径搜索问题如迷宫、棋盘覆盖二、回溯算法通用框架def backtrack(路径, 选择列表): if 满足终止条件: 记录结果 return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择框架说明组成部分说明路径已经做出的选择当前搜索路径选择列表当前可以做出的选择终止条件满足条件时记录结果并返回做选择将选择加入路径标记为已使用撤销选择回溯时恢复状态尝试其他选择三、回溯算法三个关键步骤步骤1画出回溯树将问题的所有可能解用树形结构表示每个节点代表一个选择每条路径代表一个候选解。步骤2确定回溯函数的参数和返回值参数路径、选择列表、当前状态等返回值通常返回 void通过全局变量或引用参数记录结果步骤3确定终止条件当路径满足题目要求的终止条件时将结果加入答案集合并返回四、常见回溯模板分类4.1 排列问题特点元素无重复求所有排列顺序def backtrack(路径, 选择列表): if len(路径) len(选择列表): 记录结果 return for 选择 in 选择列表: if 选择未被使用: 标记为已使用 路径.append(选择) backtrack(路径, 选择列表) 路径.pop() 标记为未使用经典题目LeetCode 46. 全排列4.2 组合问题特点元素无重复求所有组合不考虑顺序def backtrack(路径, 选择列表, 起始索引): if len(路径) k: 记录结果 return for i in range(起始索引, len(选择列表)): 路径.append(选择列表[i]) backtrack(路径, 选择列表, i 1) # 下一层从 i1 开始 路径.pop()经典题目LeetCode 77. 组合4.3 子集问题特点求所有可能的子集def backtrack(路径, 起始索引): 记录当前路径到结果集 # 每个节点都记录 for i in range(起始索引, len(选择列表)): 路径.append(选择列表[i]) backtrack(路径, i 1) 路径.pop()经典题目LeetCode 78. 子集4.4 去重问题特点元素有重复需要去重def backtrack(路径, 起始索引): if 满足终止条件: 记录结果 return for i in range(起始索引, len(选择列表)): if i 起始索引 and 选择列表[i] 选择列表[i-1]: continue # 去重同一层跳过重复元素 路径.append(选择列表[i]) backtrack(路径, i 1) 路径.pop()关键去重规则树层去重if i start_index and nums[i] nums[i-1]: continue树枝去重不需要额外判断每个元素只能用一次时4.5 分割问题特点将字符串分割成回文子串def backtrack(路径, 起始索引): if 起始索引 len(s): 记录结果 return for i in range(起始索引, len(s)): if isPalindrome(s, 起始索引, i): 路径.append(s[起始索引:i1]) backtrack(路径, i 1) 路径.pop()经典题目LeetCode 131. 分割回文串4.6 N皇后问题特点在 N×N 棋盘上放置 N 个皇后互不攻击def backtrack(行, 棋盘): if 行 n: 记录结果 return for 列 in range(n): if isValid(行, 列, 棋盘): 放置皇后 backtrack(行 1, 棋盘) 撤销皇后经典题目LeetCode 51. N皇后五、回溯算法优化技巧5.1 剪枝剪枝类型说明示例约束剪枝不满足约束条件时提前返回N皇后不放置攻击位置最优性剪枝当前路径不可能优于已知最优解时剪枝旅行商问题可行性剪枝当前路径不可能形成可行解时剪枝数独填入冲突数字搜索树剪枝利用对称性跳过等价搜索组合去重5.2 状态恢复使用全局变量记录状态时必须回溯时恢复使用函数参数传递时无需手动恢复每次调用都是独立副本5.3 记忆化优化对于有重叠子问题的回溯可使用 memo 数组缓存结果注意标准回溯问题通常无重叠子问题但某些变体如 DP 与回溯结合可使用六、回溯 vs 动态规划对比维度回溯算法动态规划核心思想深度优先搜索 回溯状态转移 最优子结构求解目标枚举所有可行解求最优解时间复杂度通常较高指数级通常较低多项式级空间复杂度递归栈深度DP 表适用场景枚举/计数/搜索最优化/计数典型问题全排列、N皇后背包问题、最长公共子序列七、回溯算法复杂度分析问题类型时间复杂度空间复杂度全排列O(n!)O(n)组合选k个O(C(n,k))O(k)子集O(2^n)O(n)N皇后O(n!)O(n)回文分割O(n·2^n)O(n)八、调试技巧打印回溯树在递归函数入口打印当前路径和选择列表记录递归深度用缩进表示递归层级便于追踪小数据测试先用 n3 或 n4 的小规模数据验证逻辑正确性检查撤销操作确保每次递归返回后状态完全恢复九、常用模板速查卡问题类型起始索引去重判断记录时机排列从 0 开始用 used 数组标记路径长度等于输入长度组合从 start_index 开始同层跳过重复路径长度等于 k子集从 start_index 开始同层跳过重复每层都记录分割从 start_index 开始无起始索引等于字符串长度N皇后从当前行开始无用 isValid 判断行数等于 n十、参考题目清单题目类型难度LeetCode 46. 全排列排列中等LeetCode 47. 全排列 II排列去重中等LeetCode 77. 组合组合中等LeetCode 78. 子集子集中等LeetCode 90. 子集 II子集去重中等LeetCode 131. 分割回文串分割中等LeetCode 51. N皇后约束满足困难LeetCode 37. 解数独约束满足困难LeetCode 39. 组合总和组合可重复中等LeetCode 40. 组合总和 II组合去重中等