网站建设工程师面试,如何制作网站图片,帝国cms如何做微网站,微信网页宣传网站怎么做
代码随想录算法训练营第二十九天 | 回溯算法总结
1. 组合问题
1.1 组合问题
在77. 组合中#xff0c;我们开始用回溯法解决第一道题目#xff1a;组合问题。
回溯算法跟k层for循环同样是暴力解法#xff0c;为什么用回溯呢#xff1f;回溯法的魅力#xff0c;用递…
代码随想录算法训练营第二十九天 | 回溯算法总结
1. 组合问题
1.1 组合问题
在77. 组合中我们开始用回溯法解决第一道题目组合问题。
回溯算法跟k层for循环同样是暴力解法为什么用回溯呢回溯法的魅力用递归控制for循环嵌套的数量
把回溯问题抽象为树形结构如图 可以直观的看出其搜索的过程for循环横向遍历递归纵向遍历回溯不断调整结果集。
优化回溯算法只有剪枝一种方法树形结构如图 剪枝精髓是for循环在寻找起点的时候要有一个范围如果这个起点到集合终止之间的元素已经不够题目要求的k个元素了就没有必要搜索了。
在for循环上做剪枝操作是回溯法剪枝的常见套路 后面的题目还会经常用到。
1.2 组合总和
组合总和一
在216. 组合总和 III中相当于在77. 组合加了一个元素总和的限制。
树形结构如图 整体思路还是一样的本题的剪枝会好想一些即已选元素总和如果已经大于n题中要求的和了那么往后遍历就没有意义了直接剪掉如图 在本题中依然还可以有一个剪枝就是77. 组合剪枝中提到的对for循环选择的起始范围的剪枝。所以剪枝的代码可以在for循环加上 i 9 - (k - path.size()) 1的限制
组和总和二
在39. 组合总和中讲解的组合总和问题和77.组合与216.组合总和III的区别是本题没有数量要求可以无限重复但是有总和的限制所以间接的也是有个数的限制。
本题还需要startIndex来控制for循环的起始位置对于组合问题什么时候需要startIndex呢
如果是一个集合来求组合的话就需要startIndex例如77.组合与216.组合总和III 如果是多个集合取组合各个集合之间相互不影响那么就不用startIndex例如17. 电话号码的字母组合 以上我只是说求组合的情况如果是排列问题又是另一套分析的套路。
树形结构如下 本题的剪枝优化如下
for (int i idx; i candidates.length; i) {// 如果 sum candidates[i] target 就终止遍历if (sum candidates[i] target) break;优化后树形结构如下
组合总和三
在组合总和II中集合元素会有重复但要求解集不能包含重复的组合。 所以难就难在去重问题上了。 为了讲解这个去重问题科普两个概“树枝去重”和“树层去重”。 “树枝去重”和“树层去重”出自代码随想录Carl 都知道组合问题可以抽象为树形结构那么“使用过”在这个树形结构上是有两个维度的一个维度是同一树枝上“使用过”一个维度是同一树层上“使用过”。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。 我在图中将used的变化用橘黄色标注上可以看出在candidates[i] candidates[i - 1]相同的情况下
used[i - 1] true说明同一树枝candidates[i - 1]使用过used[i - 1] false说明同一树层candidates[i - 1]使用过
对于去重其实排列和子集问题也是一样的道理。
1.3 多个集合求组合
在17.电话号码的字母组合中开始用多个集合来求组合还是熟悉的模板题目但是有一些细节。 例如这里for循环可不像是在77.组合与216.组合总和III中从startIndex开始遍历的。 因为本题每一个数字代表的是不同集合也就是求不同集合之间的组合而77.组合与216.组合总和III都是是求同一个集合中的组合
树形结构如下
1.4 切割问题
在131.分割回文串中我们开始讲解切割问题虽然最后代码看起来好像是一道模板题但是从分析到学会套用这个模板是比较难的。
以下是几个难点
切割问题其实类似组合问题如何模拟那些切割线切割问题中递归如何终止在递归循环中如何截取子串如何判断回文
如果想到了用求解组合问题的思路来解决切割问题本题就成功一大半了接下来就可以对着模板照葫芦画瓢。 但后续如何模拟切割线如何终止如何截取子串其实都不好想最后判断回文算是最简单的了。 除了这些难点本题还有细节例如切割过的地方不能重复切割所以递归函数需要传入i 1。
树形结构如下
子集问题
子集问题一
在78. 子集中讲解了子集问题在树形结构中子集问题是要收集所有节点的结果而组合问题是收集叶子节点的结果。
如图
认清这个本质之后今天的题目就是一道模板题了。
本题其实可以不需要加终止条件因为startIndex nums.size()本层for循环本来也结束了本来我们就要遍历整棵树。 不写终止条件会不会无限递归呢 并不会因为每次递归的下一层就是从i1开始的。 如果要写终止条件注意result.add(new ArrayList(path));要放在终止条件的上面如下
result.add(new ArrayList(path));//「遍历这个树的时候把所有节点都记录下来就是要求的子集集合」。if (startIndex nums.length){ //终止条件可不加return;}子集问题二
在90.子集II中开始针对子集问题进行去重。 本题就是78. 子集的基础上加上了去重去重我们在组合总和II也讲过了一样的套路。
树形结构如下
递增子序列
在491.递增子序列中处处都能看到子集的身影但处处是陷阱值得好好琢磨琢磨
树形结构如下 很多同学都会把这道题目和90.子集II混在一起。
2. 排列问题
排列问题一
46. 全排列又不一样了。
排列是有序的也就是说 [1,2] 和 [2,1] 是两个集合这和之前分析的子集以及组合所不同的地方。 可以看出元素1在[1,2]中已经使用过了但是在[2,1]中还要在使用一次1所以处理排列问题就不用使用startIndex了。
如图 大家此时可以感受出排列问题的不同
每层都是从0开始搜索而不是startIndex需要used数组记录path里都放了哪些元素了
排列问题二
排列问题也要去重了在47. 全排列 II中又一次强调了“树层去重”和“树枝去重”。
树形结构如下 这道题目神奇的地方就是used[i - 1] false也可以used[i - 1] true也可以
本题used数组即是记录path里都放了哪些元素同时也用来去重一举两得。
