题目
https://leetcode-cn.com/problems/increasing-subsequences/
递增子序列
程序
class Solution {
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
set<vector<int>> vec;
vector<int> res;
search(nums,0,vec,res);
return vector<vector<int>>(vec.begin(),vec.end());
}
void search(vector<int>& nums,int k,set<vector<int>> &vec,vector<int> res){
if(res.size()>=2) vec.insert(res);//如果大于两个元素，写入最终结果
for(int i=k;i<nums.size();i++){//1 for循环范围 k==0
if(res.empty()||res.back()<=nums[i]) {//满足条件
res.push_back(nums[i]);
search(nums,i+1,vec,res);
res.pop_back();
}
}
}
};
分析
1 for循环范围
- 假定当前执行到第K层，这样第K个与之后的每一个都可选
- 例：第一层，即第一个元素，可选 4 6 7 7中的任何一个，但要是选了6，下一个元素就只能在i+1,即7 7中选一个。
for(int i=k;i<nums.size();i++)
2 选中后的变化
我们定义一个向量res存这些数，只要可选就放入res中
if(res.empty()||res.back()<=nums[i]) {//满足条件
res.push_back(nums[i]);
search(nums,i+1,vec,res);
res.pop_back();
}
3 是否回溯
- 需要回溯
- 如果第一次选了4，等下要重选，第一个数选6，所以需要回溯
- 怎么回溯：res向量中弹出最后一个数就可以了
res.pop_back();
4 结果保存
在每次执行时，如果res中的个数大于2，就把这个结果放入最终结果的set中。
if(res.size()>=2) vec.insert(res);//如果大于两个元素，写入最终结果
通过本题学到什么
- 基础题，按模版写即可
- 题目要求无重复，用set则简单很多，set是无重复的集合，比如你往set里放一个1，再放一个1，set里还是只有一个1.
- 这个搜索函数的定义中，注意set传的是地址，&，传地址的作用在于，在函数中改变了这个变量的值，这个值的实际值就会被改变，因为我们要把这个结果存入SET中，所以要传地址。
- 相对而言，res向量使用形参即可，因为不需要把改变后res的值返回，只对下一层调用有影响。
