# 本周小结!(回溯算法系列一)

# 周一

本周我们正式开始了回溯算法系列,那么首先当然是概述。

关于回溯算法,你该了解这些! (opens new window)中介绍了什么是回溯,回溯法的效率,回溯法解决的问题以及回溯法模板。

回溯是递归的副产品,只要有递归就会有回溯

回溯法就是暴力搜索,并不是什么高效的算法,最多在剪枝一下。

回溯算法能解决如下问题:

  • 组合问题:N个数里面按一定规则找出k个数的集合
  • 排列问题:N个数按一定规则全排列,有几种排列方式
  • 切割问题:一个字符串按一定规则有几种切割方式
  • 子集问题:一个N个数的集合里有多少符合条件的子集
  • 棋盘问题:N皇后,解数独等等

是不是感觉回溯算法有点厉害了。

回溯法确实不好理解,所以需要把回溯法抽象为一个图形来理解就容易多了,每一道回溯法的题目都可以抽象为树形结构。

针对很多同学都写不好回溯,我在关于回溯算法,你该了解这些! (opens new window)用回溯三部曲,分析了回溯算法,并给出了回溯法的模板。

这个模板会伴随整个回溯法系列!

# 周二

回溯算法:求组合问题! (opens new window)中,我们开始用回溯法解决第一道题目,组合问题。

我在文中开始的时候给大家列举k层for循环例子,进而得出都是同样是暴力解法,为什么要用回溯法。

此时大家应该深有体会回溯法的魅力,用递归控制for循环嵌套的数量!

本题我把回溯问题抽象为树形结构,可以直观的看出其搜索的过程:for循环横向遍历,递归纵向遍历,回溯不断调整结果集

# 周三

针对回溯算法:求组合问题! (opens new window)还可以做剪枝的操作。

回溯算法:组合问题再剪剪枝 (opens new window)中把回溯法代码做了剪枝优化,在文中我依然把问题抽象为一个树形结构,大家可以一目了然剪的究竟是哪里。

剪枝精髓是:for循环在寻找起点的时候要有一个范围,如果这个起点到集合终止之间的元素已经不够 题目要求的k个元素了,就没有必要搜索了

# 周四

回溯算法:求组合总和! (opens new window)中,相当于 回溯算法:求组合问题! (opens new window)加了一个元素总和的限制。

整体思路还是一样的,本题的剪枝会好想一些,即:已选元素总和如果已经大于n(题中要求的和)了,那么往后遍历就没有意义了,直接剪掉

在本题中,依然还可以有一个剪枝,就是回溯算法:组合问题再剪剪枝 (opens new window)中提到的,对for循环选择的起始范围的剪枝。

所以,剪枝的代码,可以把for循环,加上 i <= 9 - (k - path.size()) + 1 的限制!

组合总和问题还有一些花样,下周还会介绍到。

# 周五

回溯算法:电话号码的字母组合 (opens new window)中,开始用多个集合来求组合,还是熟悉的模板题目,但是有一些细节。

例如这里for循环,可不像是在 回溯算法:求组合问题! (opens new window)回溯算法:求组合总和! (opens new window)中从startIndex开始遍历的。

因为本题每一个数字代表的是不同集合,也就是求不同集合之间的组合,而回溯算法:求组合问题! (opens new window)回溯算法:求组合总和! (opens new window)都是是求同一个集合中的组合!

如果大家在现场面试的时候,一定要注意各种输入异常的情况,例如本题输入1 * #按键。

其实本题不算难,但也处处是细节,还是要反复琢磨。

# 周六

因为之前链表系列没有写总结,虽然链表系列已经是两个月前的事情,但还是有必要补一下。

所以给出链表:总结篇! (opens new window),这里对之前链表理论基础和经典题目进行了总结。

同时对链表:环找到了,那入口呢? (opens new window)中求环入口的问题又进行了补充证明,可以说把环形链表的方方面面都讲的很通透了,大家如果没有做过环形链表的题目一定要去做一做。

# 总结

相信通过这一周对回溯法的学习,大家已经掌握其题本套路了,也不会对回溯法那么畏惧了。

回溯法抽象为树形结构后,其遍历过程就是:for循环横向遍历,递归纵向遍历,回溯不断调整结果集

这个是我做了很多回溯的题目,不断摸索其规律才总结出来的。

对于回溯法的整体框架,网上搜的文章这块一般都说不清楚,按照天上掉下来的代码对着讲解,不知道究竟是怎么来的,也不知道为什么要这么写。

所以,录友们刚开始学回溯法,起跑姿势就很标准了。

下周依然是回溯法,难度又要上升一个台阶了。

最后祝录友们周末愉快!

如果感觉「代码随想录」不错,就分享给身边的同学朋友吧,一起来学习算法!


上次更新:: 11/30/2023, 10:16:49 AM
@2021-2022 代码随想录 版权所有 粤ICP备19156078号