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