【代码随想录|回溯算法排列问题】

491.非减子序列

题目链接. - 力扣（LeetCode）

这里和子集问题||很像，但是这里要的是非递减的子序列，要按照给的数组的顺序来进行排序，就是如果我给定的数组是[4,4,3,2,1]，如果用子集||的做法先进行排序得到[1,2,3,4,4]，那我就会收集得到[1,2][2,3][3,4][4,4]等等子集，但是这道题的话我得到的集合只有[4,4]，就是这里我只从我给的数组里进行排序，给非递减的子集。

去结点操作：

一、进行树层去重

但是用之前的方法排序后看used数组里面我两个元素到底用没用已经不可行了，所以这里加了一个set数组，来进行去重，只要我没有和之前相同的元素那就继续取

（这里不用回溯掉used  我觉得是之前回溯是因used定义是在主函数里面，你不手动回溯那个值不会主动变为0，而这里直接定义函数里，在每一层循环外面，我一进去递归就重开了一个set数组，天然的就不用进行回溯了）

二、去掉递减的结点

去结点的时候，我们把我们遍历到的节点和收集到的结点进行比较，如果这个节点比我们收集到的结点小了，那么我们硬塞进去就不是递增序列了，所以直接continue进行收集下一个结点。

class Solution {
public:
vector<int>path;
vector<vector<int>> result;
void backtracing (vector<int>& nums,int startindex){if(path.size()>1){result.push_back(path);//子集在2到2以上再进行收集}unordered_set<int> used;//每一层都会重置usedfor(int i=startindex;i<nums.size();i++){if(!path.empty()&&nums[i]<path.back()||used.find(nums[i])!=used.end()){continue;//去掉要进行递减的结点和树层去重}path.push_back(nums[i]);used.insert(nums[i]);//把nums[i]的值放used里面好进行判断到底用没用过backtracing (nums,i+1);path.pop_back();}
}vector<vector<int>> findSubsequences(vector<int>& nums) {backtracing (nums,0);return result;}
};

46.全排列

题目链接https://leetcode.cn/problems/permutations

要求是同一个数不能重复选取嘛，所以要用到used数组

这个是排列问题，需要返回和传进来数组大小相等的全排列数组，所以排列问题就不用设置startindex了，因为不用对前面的数进行去重，但是要设置一个used数组，不能重复选择同一个元素。

class Solution {//正确代码
public:
vector<int>path;
vector<vector<int>>result;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;}path.push_back(nums[i]);used[i]=true;backtracking(nums,used);path.pop_back();used[i]=false;}}vector<vector<int>> permute(vector<int>& nums) {vector<bool>used(nums.size(),false);backtracking(nums,used);return result;}
};

 注意这里只能是递归到used数组为true的时候continue进行下一次选取，如果像我一样直接对used等于0来进行判断的话，那它等于1的时候就不会有限制，就会一直进行递归进行循环，直到栈空（离大谱..）

for(int i=0;i<nums.size();i++){//错误代码if(used[i]==false){path.push_back(nums[i]);used[i]=true;}backtracking(nums,used);path.pop_back();used[i]=false;}

47.全排列||

题目链接https://leetcode.cn/problems/permutations-ii

这道题和46.全排列不太一样的就是这里给的nums数组有重复值，比如nums给[1,1,2]，那么如果我按没有重复数的做法来做的话就会有两个[1,1,2]，那这里就是不允许的，所以我们要在上一道题的基础上多进行一次去重，就是像组合问题一样进行树层去重，同一树层上的数continue不再选取。

class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& nums, vector<bool> used) {if (nums.size() == path.size()) {result.push_back(path);//到了nums大小就收集到result，然后返回return;}for (int i = 0; i < nums.size(); i++) {if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)continue;//树层去重if (used[i] == true)//选过的不再重复选continue;path.push_back(nums[i]);used[i] = true;backtracking(nums, used);used[i] = false;path.pop_back();}}vector<vector<int>> permuteUnique(vector<int>& nums) {vector<bool> used(nums.size(), false);sort(nums.begin(), nums.end());//把nums排序used数组好进行比较进行树层去重backtracking(nums, used);return result;}
};