给定一个整数数组，你的任务是找到数组中长度至少为2的所有递增子序列。示例：输入：[4,6,7,7]输出：[[4,6],[4,7],[4,6,7],[4,6,7,7],[6,7],[6,7,7],[7,7],[4,7,7]]解释：给定数组的长度不会超过15。数组中整数的范围是[-100,100]。鉴于数组可能包含重复的数字，相等的数字应该被认为是递增的情况。这个递增子序列的思想更像是取一个有序的子集。而且这道题还要求不能存在相同的递增子序列。这是另一个子集，它是重复数据删除。是不是不由自主地想到刚才说的90.SubsetII。就是因为太像了，要多注意区别，不然就掉坑里了！在90.SubsetII中，我们使用排序，加上一个tag数组来达到去重的目的。本题求自增子序列，原数组不能排序，排序后的数组都是自增子序列。所以之前的去重逻辑不能用了！本题给出的例子依然是有序数组[4,6,7,7]，这样更容易误导大家按照排序的思路。为了形成鲜明的对比，我以数组[4,7,6,7]为例，抽象成树形结构如图：增量子序列1回溯三部曲递归函数参数这道题是要找到一个子序列，显然一个元素是不能重复使用的，所以需要startIndex来调整下一层递归的起始位置。代码如下：vector>result;vectorpath;voidbacktracking(vector&nums,intstartIndex)终止条件这道题其实和子集问题类似，同样需要遍历树结构去寻找每一个节点，所以像回溯算法：子集问题！，可以不加终止条件，每次startIndex都会加1，不会无限递归。但是，这个问题的收集结果是不同的。该题要求增量子序列大小至少为2，所以代码如下：if(path.size()>1){result.push_back(path);//注意这里没有加return，因为你需要取树上的所有节点}单层查找逻辑从图中可以看出，同一父节点下同一层已经使用过的元素不能再次使用。那么单层查找代码如下：unordered_setuset;//使用set去重本层的元素for(inti=startIndex;i>result;vectorpath;voidbacktracking(vector&nums,intstartIndex){if(path.size()>1){result.push_back(path);//这里注意不要加return，而是取树上的节点}unordered_setuset;//用set去重本层的元素for(inti=startIndex;i>findSubsequences(vector&nums){result.clear();path.clear();回溯(nums,0);returnresult;}};优化上面的代码我使用了unordered_set来记录这一层的元素是否被复用哈希，效率高了很多。注意标题说取值范围是[-100,100]，所以可以用数组来哈希。程序运行时会频繁插入unordered_set，需要对unordered_set进行hash映射（即通过hash函数将key映射为唯一的hash值）。比较费时，而且每次重新定义set和insert，底层的symbols表也要相应的扩容，也比较麻烦。那么优化后的代码如下：//version2classSolution{private:vector>result;vectorpath;voidbacktracking(vector&nums,intstartIndex){if(path.size()>1){result.push_back(path);}intused[201]={0};//这里使用数组进行去重操作。标题说取值范围是[-100,100]for(inti=startIndex;i>findSubsequences(vector&nums){result.clear();path.clear();backtracking(nums,0);returnresult;}};这段代码在leetcode上提交，比第一版要费时很多。正如哈希表中所说：总结！（每个总结必成经典），arrays，sets，maps都可以作为哈希表，map和set都可以做数组做的事情，但是如果取值范围小的话，可以用数组作为尽可能多。综上所述，这道题的所有解法都说是深度优先搜索，但我更倾向于说是用了回溯法，我也完全用回溯法的逻辑来分析这道题。90.SubsetII这道题相信你看的到处都是，但是处处都是陷阱。对于已经养成了固定型思维或者套用了模板的同学来说，这道题起到了很好的警示作用。更重要的是，拓展了大家的思路！打酱油，如果觉得《代码乱录》很干，请帮Carl宣传一下！本文转载自微信公众号“码随机记录”，可使用以下二维码关注。转载本文请联系CodeCaprice公众号。
