刷了一天回溯算法

由于发现自己递归的回溯部分还是不太清楚，今天就特意抽出一整天的时间来练习回溯算法。

练习方式：把《代码随想录》上面第九章回溯算法这一章的所有题目，总共有十四道题目都做了一遍。

32 分钟前#37 解数独困难2 次

4 小时前#51 N 皇后困难3 次5 小时前#47 全排列 II中等1 次5 小时前#46 全排列中等1 次5 小时前#491 递增子序列中等3 次7 小时前#90 子集 II中等3 次8 小时前#78 子集中等1 次8 小时前#93 复原 IP 地址中等1 次8 小时前#131 分割回文串中等1 次10 小时前#40 组合总和 II中等4 次11 小时前#39 组合总和中等1 次12 小时前#17 电话号码的字母组合中等2 次12 小时前#216 组合总和 III中等1 次12 小时前#77 组合中等2 次

回顾复盘一下

77. 组合

这个题以前是直接用python的combination做的，但是总感觉用库心里不踏实，没有学到精髓。也不利于递归思维的提升。所以就看书学了学回溯算法。

感觉回溯算法的核心精髓，就是：每次递归操作完了之后都会撤销当前操作。，就比如这段代码里面的 lst.pop()，忽然感觉以前的自己实在是太屑了。不知道在遍历决策树的时候怎么倒退，干着急也没办法，原来就是这么简单，感觉很妙。

216. 组合总和 III

这个题偷了个懒。感觉和第一题有点相似了。就调了个库

17. 电话号码的字母组合

这个题踩了个坑WA了一下，传入空字符串的时候居然回出错，于是就加了个特殊判断。

这个题目看了之后梦回小学时代，那个时候我还在用诺基亚。题目就是用一个九键手机，给出一串数字，给出所有的能匹配出来的字母，这个题好像和实际的现实还不太一样，因为现实情况实际上是想打出一个b，要按两下2才行。这个只是直接求组合的所有可能了。就是按一下2，abc都有可能了。

想起来以前周赛好像做过一个题，是给出了很长很长一串数字，问可能打出多少种字母，那个题的配图和这个题的配图居然是一样的我记得。但是这个题好像感觉不如那个题难，那个题当时是用动态规划来解决的。当时居然还做了快一个小时，当时那个题的dp递推式子居然是刚好碰出来的。

39. 组合总和

这个题不一样的点在于里面的元素可以无限次被选择。

做到这道题的时候就感觉自己在22年五月份还是四月份的时候，也就是刷剑指offer1的时候，自己当时的很多这种组合问题好像也遇到过，当时就是全用的combination全偷懒做的，一遇到变种，发现不能偷懒，就不会了，当时就直接抄别人的答案提交了。但是打开这道题的时候找不到自己的提交记录了，可能是剑指offer上面的题有重复的一样的题，题源地址可能不是一个。

40. 组合总和 II

这个题总是超过时间限制

这个题的特点是：结果的每一个组合里可以有重复的数字，但是！！所有的结果里不能有重复的组合。。。

就是有一个组合 [1, 1, 2] 是合法的，但是不能有两个 [1, 1, 2]。

这个我和书上的最开始的做法很一致，一上来先拍了序，但是排序之后怎么去重是个大问题，最开始我是直接遍历所有组合，单纯用一个集合放在最外层来去重，但是发现这样总是超时。

其实应该是在遍历决策树的时候，直接用同层重复数字来剪枝去重，不仅达到了去重的效果，而且还达到大大大大节省时间的效果。

这里的同层去重就是在内层放一个set，就是刚好在for的外一层的地方。然后先检测是否在集合里就行了。

131. 分割回文串

判断一个字符串是不是回文的，直接用python语法糖了。本质上都是用的线性的时间复杂度。

这个题问的意思是，在一个字符串的各个缝隙位置上放若干个隔板，隔板分割出来的每一个字符串都是回文的。

有多少种放隔板的方式。

我规定的下标是在对应i下标元素之后，与i+1之间放隔板。

想了想执行一次之后就通过了

93. 复原 IP 地址

这个题是把所有可能的IP地址返回出来，就是不停的加点，和上一个题有点像。

这个题里面有一些特殊情况的处理。

78. 子集

这题就是获取一个集合的幂集，以前做这个题的时候我发现自己是用combination偷懒了。这次好好做一下。

这个做的时候懵了一下，看了一下书上画的图才意识到，原来是在决策树上每走一步都记录添加。

这个不是for循环横向扩展决策树宽度了。而是一个二叉树的形状，要不要当前位置了。

90. 子集 II

这个题是变成了集合里有重复元素了，然后返回幂集。

答案里面可以有 [1, 1, 2] 这样的子集，但是不能有重复的子集，就不能有两个[1, 1, 2]。这又成了去重问题了

这个去重问题也是，先排序，然后再对决策树同层去重。

491. 递增子序列

这个题目就如题的名字一样简洁，获得一个数组的所有的递增的子序列。因为递增性质，所以所有子序列的长度必须是大于等于2的。

这个题也是，发现得去重，去重就挺麻烦的，发现是同层去重。

然后记录答案的时候，是只要path数组的长度一旦大于2，就会记录。

最开始看到这个题我想的是，这不直接来个二重循环就可以了吗。后来逝了一下才发现，不行。因为二重循环里面那一层没法做到间断跳跃的选择。这个题WA了两次。边界条件还得处理。

46. 全排列

这个题好像也可以直接调用itertools里面的全排列直接写，但是就失去练习的意义了。所以特意要学习一下回溯怎么实现全排列。

这个决策树就是一个完整的树了，像之前的题一样，左边深右边空。

记录答案的时候就刚好是path数组写满了的时候就记录。

for循环里面写的也是，直接遍历满，要排除自己。

以前大二的时候刚做行列式的程序就用到了全排列算法，当时自己不知道python内置库实现了，就自己瞎搞，搞的代码又臭又长，空间复杂度On！，直接生成了一个多叉树，也根本不会回溯，就无奈又把多叉树改成了三叉链表。增加了指向父亲节点的指针。特别特别麻烦，居然还搞了一下午。现在看看以前的自己真的好憨憨。但也没办法。只是感觉过去的自己学习的进度和效率低了。

现在看看这个全排列算法，感觉不怎么难。看着这么几行代码，居然还感觉有点简单。

也许我应该有这样一个警醒：当我特别想做出一个东西，但是我的算法卡脖子了，然后我硬是去用自己的方法做。虽然可能很有成就感，但是这可能说明我的算法技能和知识有着严重漏洞。

47. 全排列 II

这个题就是在上一个题的基础上，要给出全排列的序列里面有了重复的元素了。

这个去重又有点麻烦了。搞了挺长时间。

递归参数搞了两个数组，一个是记录选择下标的数组，一个是记录选择的元素的数组，

选择下标的数组不能重复选择，选择元素的数组在树的同层也是要去重的。

51. N 皇后

这个N皇后问题，以前做过，一看提交记录发现，竟然恰好是上一年的这个月

提交结果执行用时内存消耗语言提交时间备注通过72 ms15.3 MBPython32022/06/16 17:10

添加备注




通过996 ms15.8 MBPython32021/06/13 18:03

DFS，减少了搜索范围




超出时间限制N/AN/APython32021/06/13 16:26

上一年的今天左右相差了三天，回忆起以前这个题当时搞了好像将近两个多小时，这次好像半小时就搞过了。看来掌握回溯就是好啊。

并且当时的运行时间也好多。

现在写的时候，就判断斜着相撞的时候，绕了一下。

字符串处理也感觉得心应手了。

37. 解数独

这个解数独，以前大一的时候2020年上半年，也就是刚开始学python的那半年搞出来过，当时还没学算法，还没学数据结构，就是想搞出来解决数独的问题。当时也还做了框图。只是没有用递归。做了整整大半天。

后来知道了leetcode，发现了有解数独这个题，只是没想到格式居然是字符串格式，太麻烦了，就一直没做。

今天终于把这个题给解决了。

判断数独整体是否有效的时候还是出了点小bug。

整个回溯递归的时候逻辑也遇到了点问题，发现自己明明写好了，但是最后好像又全给擦掉了，就用了一个success变量。但是又发现最后填写的数全都变成9了，原来是自己在递归for循环里忘了break了。还是有好多小细节问题。

总结

今天用了整整一天的时间又弥补了一下以前算法一直欠缺的地方，感觉很有收获。

这些去重的问题，层间去重和树枝下去重，书里讲的真的挺清楚的。这个书里给出的做题顺序也真的不错。

可能以后有时间还是要回头继续做这些题，时间长了可能又会变得生疏。也许一年之后，我又会变成一个更强的自己。回头看到自己现在写的代码可能还是不够好。