回溯算法06（总结+leetcode332,51,37）

参考资料：

https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html

力扣这三题暂时不在本篇笔记中贴代码了，有兴趣的可参考332.重新安排形成、N皇后、解数独

总结：

画树形图分析题目

用途：回溯算法是用 递归实现的多重for循环。（当有用多重for循环暴力求解的想法时，就考虑用回溯）

效率：本质是穷举，效率低，可剪枝提高效率

回溯三部曲：

        1. 回溯函数参数。——一般nums[],（看情况使用startIndex,target）

        2. 终止条件。——控制for循环层数

        3. 单层遍历过程。——处理节点，backTracking()，回溯

去重：题目的数据中有重复元素，就考虑“树层去重”，使用若可排序则用used[]数组，否则用HashSet

剪枝：单层遍历的条件里面写剪枝条件

常考题型：

        1.组合：有重复元素时先sort ， 控制startIndex

        2.切割：思路同“组合”，注意细节（模拟切割线、截取子串...）

        3.子集：收集all节点，可不额外加终止条件（for循环判断条件中会终止）

        4.排列：不用startIndex，用used[]

        5.棋盘：...

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}
//参考 代码随想录