回溯算法专题
回溯算法是一种通过试错来寻找问题解的算法。当发现当前选择不能得到有效解时，就回退并尝试其他选择。回溯算法本质上是一种深度优先搜索，通常用于解决组合、排列、子集等问题。
目录
基础理论
组合问题
分割问题
子集问题
排列问题
其他问题
学习要点
- 回溯算法的基本思想：试错 + 回退
- 回溯三部曲：递归函数参数、终止条件、单层搜索逻辑
- 组合与排列的区别
- 去重技巧：树层去重 vs 树枝去重
- 剪枝优化：提前终止无效搜索
- 回溯模板的灵活运用
核心思想
- 深度优先搜索：沿着一条路径深入搜索，直到无法继续
- 状态回退：当发现当前路径无法得到解时，回退到上一个状态
- 剪枝优化：通过条件判断，避免无效的搜索分支
- 去重处理：在有重复元素的情况下，避免生成重复的解
经典模板
cpp
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果;
}
}问题分类
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等