回溯算法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(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
//参考 代码随想录原文地址：https://blog.csdn.net/weixin_62372284/article/details/139195786
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！