LeetCode 491. 递增子序列（C++）

给定一个整型数组,你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

示例:

输入: [4,6,7,7]

输出: [[4,6],[4,7],[6,[7,7]]

说明:

给定数组的长度不会超过15。

数组中的整数范围是?[-100,100]。

给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。

思路：采用循环递归的思想。

比如输入[3,4,5,6]

从3开始，放入tmp中，只要后面的数比tmp最后一个数大，则加入tmp

因此第一次结果分别为[3,4]、[3,5]、 [3,6]

当递归结束时，把tmp最后一个元素取出：

例如，当tmp=[3,6]时，此时k=3，递归结束，将6取出，tmp=[3,5]，

此时，k=2，i=k递归结束，取出5,tmp=[3,4]，接着i=3,6]

因此最终输出的顺序是:[3,5]、[3,6]、[3,6]、 [3,6]

[4,5]、[4,6]、[4,6]、[5,6]

C++

class Solution {

public:

void DFS(vector& nums,set>& res,vector& tmp,int k)

{

if(tmp.size()>=2)

{

res.insert(tmp);

}

for(int i=k;i

{

if(tmp.empty() || nums[i]>=tmp.back())

{

tmp.push_back(nums[i]);

DFS(nums,res,tmp,i+1);

tmp.pop_back();

}

}

}

vector> findSubsequences(vector& nums)

{

int n=nums.size();

set> res;

vector tmp;

DFS(nums,0);

return vector>(res.begin(),res.end());

}

};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!