一、代码随想录中讲解的各个部分的概括
1.什么是回溯法
用于解决特定问题(无法用for循环暴力搜索的问题)的递归法
2.回溯法的效率
不高效,完全是暴力穷举,专门解决无法用for循环暴力搜索的问题
(能找到解法就不错了,还要什么自行车啊)
3.回溯法解决的问题
一共五个种类:排列、组合、切割、子集、棋盘
4.如何理解回溯法
所有回溯问题都可以抽象为N叉树,N(宽度)是每一个节点的搜索集合,深度是递归深度
(我的个人理解:
如果用嵌套for循环,
嵌套循环有几层是不确定的
【不是循环次数不确定,而是嵌套层数不确定】,
嵌套层数的拓展用递归来实现,
写是写不出来的,
所以是树状结构)
5.回溯法模板
1.函数(无返回值,参数多) + 2.if(终止){收集+return} + 3.for(搜索集){处理;递归;回溯}
二、比较重要的部分(在理解的基础上)
1.解决的问题(遇到哪些问题要用)
这个估计是要背下来的,
我目前概括不出来有什么容易识别的共同特点:
- 组合问题:N个数里面按一定规则找出k个数的集合
- 切割问题:一个字符串按一定规则有几种切割方式
- 子集问题:一个N个数的集合里有多少符合条件的子集
- 排列问题:N个数按一定规则全排列,有几种排列方式
- 棋盘问题:N皇后,解数独等等
2.回溯法模板(遇到了回溯问题的时候怎么解决)
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果}
}
如果有大佬看见了我思路上的错误或代码不完善的地方,请帮助指出,刷题阶段非常希望能有快速提升