1.理论基础
回溯和递归是相辅相成的.
- 隐藏在哪里呢?
通常是递归函数的下面.
二叉树的递归就是,只不过有的题目用到了回溯,有的没用到. - 效率
并不是高效的算法,纯暴力 - 能解决的问题:
- 组合问题
组合是强调没有顺序的
给你一个集合[1,2,3,4]问你大小为2的组合.比如[1,2];[2,3]... - 切割问题
给你一个字符串,问你有几种切割方式/如何切割才能保证子串都是回文子串 - 子集问题
如集合[1,2,3,4]的全部子集 - 排列问题
排列是强调有顺序的 - 棋盘问题
N皇后/解数独
- 组合问题
- 回溯法抽象成图来理解
回溯法可以抽象成一个树形结构const backtracking = ()=>{ if(终止条件){ //收集结果 return; } for(放集合的元素集){ //处理节点 //递归函数 //回溯操作 } }
image.png
2. 77.组合
如果只是单纯用for循环嵌套,少了还好说,如果要的是n=100,k=50的所有集合呢?
- 这题的startIndex不是下标,而是具体的值,所以是从1开始
-
过程:
image.png - 以及在leetcode上设全局变量记得要清空,不然不同case会相互影响.
