LC吐血整理之Backtracking篇

Posted on | In
人生苦短 我学python

所有题解方法请移步 github-Leecode_summary

78. 子集

今天的收获很大，知道了我不适合做算法 :) 　　刚开始用最原始的方法，感觉会写的很复杂，然后看分类Backtracking，突然想到是不是可以用回溯，然后我折腾了快两个小时 :)，最后还是差一点，尽管很绝望，能学到的东西还是蛮多的… 　　我最难理解的是回溯算法，所以还是在这里详细的解释一下。其中回溯算法可以以 深度优先遍历 和 宽度优先遍历为基础，详情见右下图(都是神仙方法啊)： 　　看了很久，跟树结合很巧妙，在搜索过程可根据约束条件剪枝（避免不必要的搜素）

  • 回溯算法（深度优先遍历）：
    a

  • 可以想象成一棵树，类似树的遍历：
    b

90.子集II

既然题目要求不能有重复的子集，就要从两个方面着手：
1. 找出所有子集->筛选
2. 找子集的过程中主动避免重复
　　我就只会做最笨的方法咯，但肯定是有比较trick的方法…（多看多想，总结一下），比如统计频数法，又比如数组排序再组合
今日份的Tips: list的相等问题： 

1
2
3
4
5
6
7
>>> list1 = [1, 2, 3, 4]  list2 = [1, 2, 3, 4]  list3 = [4, 3, 2, 1]
>>> list1 == list2        #  判断严格相等 (元素及顺序相等)
True
>>> list1 == list3       
False
>>> sorted(list1) == sorted(list3)     # 只要求元素相等  
>>>list1.sort() == list3.sort()     #sorted()生成新的数组/list.sort()对自身改变

77. 组合

　　这个题目就是子集的子集？？，还是“换汤不换药”，遍历会了什么都好做，只不过是往上加点条件罢了..不过多撰述了..

39.组合总数

用最笨的方法 超最长的时 >< 　　刷题刷到现在，看了题解回溯、剪枝，终于有点感觉，在书里面见识的算法是实实在在可以用来解决问题的~ 做题的时候在想，怎么能在append的同时鉴别是否重复呢，但我真的想不到…好菜啊…题解还有动态规划解决方案可以思考一下 题解两种遍历：
1 全部遍历(包含重复数组)，逐个判断是否符合要求
2 从根源上避免重复数组
总算是发现了我能理解且复现的方法: 树与剪枝 参考代码
另外动态规划方法也蛮不错的，要领会其思想

组合总数II

思考：1.遍历不包括自身 2.怎么剪枝