(一) 排列与组合
通常通常循环来做暴力枚举是有局限性,通过回溯算法来做枚举往往会更加优雅,回溯算法中两个重要的模型便是组合模型与排列模型。
题目 | 思路描述 |
---|---|
LC0077. 组合 LC0078. 子集 |
组合和子集要求的答案都是顺序无关的,因而与排列不同的地方在于,枚举组合的时候,for 循环的起始下标是递增的 |
LC0040. 组合总和 II LC0090. 子集 II |
对给定的数组排序,然后回溯的时候如果当前元素与上一个元素相等则跳过当前元素,以此实现去重的效果,两道题的去重套路都是一模一样的 |
LC0216. 组合总和 III | 枚举固定长度的组合数,通过排序给定数组去重,通过数据范围均为正数故相加不允许超过指定数值 n 来做剪枝 |
LC0046. 全排列 LC0047. 全排列 II |
由于不像组合问题那样「每次递归进入更深层之后枚举的起始下标会递增」,在求排列问题的时候需要额外的开辟 vist 数组维护已经访问的元素,去重思路与上面大同小异。 |
LC0491. 递增子序列 | 本题的去重非常有技巧性,因为这个递增子序列是要保序的,因而不可以通过排序去重,那么需要分类讨论:(1)前选后选,(2)前不选后选,(3)前选后不选,(4)前不选后不选,(2)与(3)其实能合并归为一种的,因而维护上一个选择的元素,递归时分为选择当前元素与不选当前元素两种情况讨论即可。 |
(二) 去重与剪枝
当有重复元素的时候,去重往往是通过排序来实现的,但当需要枚举子序列等需要保序的答案时,基于排序的去重思路便不好使了。如果给定了约束条件,一般可以通过约束条件来做剪枝思路。
支持作者
![](/i/l/?n=22&i=blog/1784910/202208/1784910-20220814154614203-891802546.png)