代码随想录算法【Day22】
Day22
回溯算法
回溯与递归是什么关系？
有递归就会有回溯，递归函数的下面就是回溯的逻辑，有时回溯就是指递归，没有完全都是回溯的函数
回溯搜索本质上是暴力搜索
回溯法解决的问题：
组合问题 组合数字
切割问题 字符串有几种切割方式
子集问题 列出所有子集
排列问题
棋盘问题 N皇后，解数独
这些问题用暴力法for嵌套循环是解决不了的
如何理解回溯法？
所有的回溯法都可以抽象成一个树形结构
回溯法模板
void backtracking(参数){
if(终止条件){
在叶子结点收集结果
return //结束当前函数调用
}
//单层搜索逻辑
for(集合元素){
处理结点;
递归函数;
回溯操作; //撤销处理结点的情况
}
return
}