html5 服装网站,微信小程序的代码,新的数据新闻,网站建设 沈阳这道题的难点依旧是去重#xff0c;但是与之前做过的子集类问题的区别就是#xff0c;这里是求子序列#xff0c;意味着我们不能先给数组中的元素排序。因为子序列中的元素的相对位置跟原数组中的相对位置是一样的#xff0c;如果我们改变数组中元素的顺序#xff0c;子序…这道题的难点依旧是去重但是与之前做过的子集类问题的区别就是这里是求子序列意味着我们不能先给数组中的元素排序。因为子序列中的元素的相对位置跟原数组中的相对位置是一样的如果我们改变数组中元素的顺序子序列也会发生改变。那么我们就不能使用之前用到过的去重方法此题需要使用道哈希表这样就可以实现去重的功能。哈希表的使用我们之前也练过不少题这里就不详细说明了忘记的同学可以看一下之前的博客。需要注意的是我们需要在每一层递归中都定义一个新的哈希表原因在于往下递归子序列可以取重复的元素但是在同一层递归的for循环中遍历时需要跳过重复的元素。其他的点比较好懂大家可以结合我下面的代码及详细注释理解此题。
代码及详细注释如下
class Solution {
public:vectorint path;vectorvectorint result;void backtracking(vectorint nums,int start){//注意题目说了至少两个元素if(path.size() 2){result.push_back(path);} //终止条件if(start nums.size()){return;}//每一层递归都需要定义一个新的哈希表unordered_setint 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();//注意哈希表并不需要回溯因为每一层都有专门的哈希表来负责去重}}vectorvectorint findSubsequences(vectorint nums) {result.clear();path.clear();backtracking(nums,0);return result;}
};
