欢迎关注个人公众号:爱喝可可牛奶
LeetCode算法训练-回溯总结
适用问题
- 组合问题:N个数里面按一定规则找出k个数的集合
- 排列问题:N个数按一定规则全排列,有几种排列方式
- 切割问题:一个字符串按一定规则有几种切割方式
- 子集问题:一个N个数的集合里有多少符合条件的子集
- 棋盘问题:N皇后,解数独等等
通用模板
result 存放结果集
path 某个符合条件的结果
void backtracking(参数) {
if (终止条件) {
result.add(path);
return;
}
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
处理节点;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
}
个人理解
-
回溯和递归紧密相联,有递归就有回溯
-
回溯的过程可以抽象为一个回溯树,要搞清楚题目要求的是分支节点、叶子节点、还是所有节点
-
去重 回溯树的同一个树枝去重(用全局used数组) 同一个树层上去重(for循环外的局部used数组)
-
画回溯树找条件写代码,什么时候要添加结果,什么时候要continue,要不要以及能不能对原始数据集排序
-
剪枝优化 什么情况下不用再递归树枝不用递归树层,这时可直接在for循环中给出限制条件
-
回溯函数遍历树枝,for循环++遍历树层