哈尔滨网站建设nsstd.com网站底部友情链接

这道题的难点依旧是去重，但是与之前做过的子集类问题的区别就是，这里是求子序列，意味着我们不能先给数组中的元素排序。因为子序列中的元素的相对位置跟原数组中的相对位置是一样的，如果我们改变数组中元素的顺序，子序列也会发生改变。那么我们就不能使用之前用到过的去重方法，此题需要使用道哈希表，这样就可以实现去重的功能。哈希表的使用我们之前也练过不少题，这里就不详细说明了，忘记的同学可以看一下之前的博客。需要注意的是，我们需要在每一层递归中都定义一个新的哈希表，原因在于：往下递归子序列可以取重复的元素，但是在同一层递归的for循环中遍历时需要跳过重复的元素。其他的点比较好懂，大家可以结合我下面的代码及详细注释理解此题。

代码及详细注释如下：

class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& nums,int start){//注意题目说了至少两个元素if(path.size() >= 2){result.push_back(path);}    //终止条件if(start >= nums.size()){return;}//每一层递归都需要定义一个新的哈希表unordered_set<int> uset;for(int i = start;i < nums.size();i++){//去重操作if((path.empty() != 1 && nums[i] < path.back()) || uset.find(nums[i]) != uset.end()){continue;}uset.insert(nums[i]);path.push_back(nums[i]);backtracking(nums,i + 1);path.pop_back();//注意哈希表并不需要回溯，因为每一层都有专门的哈希表来负责去重}}vector<vector<int>> findSubsequences(vector<int>& nums) {result.clear();path.clear();backtracking(nums,0);return result;}
};