代码随想录算法训练营第二十九天|491.非递减子序列、46.全排列、47.全排列II

491.非递减子序列

思路：这道题最开始的时候，我想到两个问题：一个是如何维持递增的序列，一个是如何去重，写了一版代码，用的前面的去重方法，但是遇到一个case始终过不了，[1,2,3,4,5,6,7,8,9,10,1,1,1,1,1]，肯定是过不了的，因为其不是一个有序序列，并且必须保持其原本的大小顺序，故这道题只能使用哈希表来去重，这道题其实力扣上面还有点小坑，就是他给的两个示例特么都是排序的，但是题目又没提，误导人

错误的思考：

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums,int index,vector<bool>& used){if(path.size()>=2){result.push_back(path);}if(index>=nums.size()){return;}for(int i=index;i<nums.size();++i){if(!path.empty() && path.back()>nums[i]) continue;if(i>0&& nums[i-1]==nums[i]&& used[i-1]==false)continue;path.push_back(nums[i]);used[i]=true;backtracking(nums,i+1,used);used[i]=false;path.pop_back();}}vector<vector<int>> findSubsequences(vector<int>& nums) {result.clear();path.clear();vector<bool> used(nums.size(),false);backtracking(nums,0,used);return result;}
};

正确写法：

又学会一种新的去重同一层的方法！

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums,int index){if(path.size()>=2){result.push_back(path);}if(index>=nums.size()){return;}unordered_set<int> myset;for(int i=index;i<nums.size();++i){if((!path.empty() && nums[i]<path.back())||myset.find(nums[i])!=myset.end()) continue;myset.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;}
};

46.全排列

思路：第一次接触全排列的问题，体会其与组合，分割问题的不同之处！

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums,vector<bool>& used){if(path.size()==nums.size()){result.push_back(path);return;}for(int i=0;i<nums.size();i++){if(used[i]==true) continue;used[i]=true;path.push_back(nums[i]);backtracking(nums,used);used[i]=false;path.pop_back();}}vector<vector<int>> permute(vector<int>& nums) {result.clear();path.clear();vector<bool> used(nums.size(),false);backtracking(nums,used);return result;}
};

47.全排列II

思路：这道题就是把前两道题的技巧结合起来了！其这道题可以用used这个数组直接进行去重，其实对于排列问题使用的used数组就是用来标记当前是否使用过的！

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums,vector<bool>& used){if(path.size()==nums.size()){result.push_back(path);return;}unordered_set<int> myset;for(int i=0;i<nums.size();++i){if(used[i]==true||myset.find(nums[i])!=myset.end()) continue;myset.insert(nums[i]);used[i]=true;path.push_back(nums[i]);backtracking(nums,used);used[i]=false;path.pop_back();}}vector<vector<int>> permuteUnique(vector<int>& nums) {result.clear();path.clear();vector<bool> used(nums.size(),false);backtracking(nums,used);return result;}
};