代码随想录算法训练营第二十四天| 回溯 491.递增子序列 46.全排列 47.全排列 II

491. 非递减子序列

?此前通过used数组去重的操作的前提是需要首先给数组排序，本题不可以，因为求递增子序列时，原先的序列并不是一定递增的，此时进行排序后，此时递增子序列会包含其他原先不是原先数据的子序列。

递归参数：index一定是需要的，记录下一层递归分割的起始位置。

递归终止条件：由N叉树可以看出，当子集内个数大于1的时候便可以收获结果

单层搜索的逻辑：在同一树层中，不需要重复读取相同的树，需要对其剪裁，由于不能使用used数组，可以使用哈希判断当前树层是否存在相同的数，unordered_set<int> uset; 是记录本层元素是否重复使用，新的一层uset都会重新定义（清空），所以要知道uset只负责本层！还需要判断树枝上的树是否会小于path最后一个数，如果小于了就不是递增子序列了

?

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    void backtracking(vector<int> &nums,int index){
        if(path.size()>1)res.push_back(path);
        unordered_set<int> hash;
        for(int i=index;i<nums.size();i++){
            if(!path.empty()&&nums[i]<path.back()||hash.find(nums[i])!=hash.end())continue;
            hash.insert(nums[i]);
            path.push_back(nums[i]);
            backtracking(nums,i+1);
            path.pop_back();
        }

    }

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        path.clear();
        res.clear();
        backtracking(nums,0);
        return res;
    }
};

46. 全排列

递归函数参数:首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。但排列问题需要一个used数组，标记已经选择的元素，如图橘黄色部分所示:

?

?递归终止条件:当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。

单层搜索的逻辑:排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。而used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    void backtracking(vector<int>&nums,vector<bool> used){
        if(path.size()==nums.size()){
            res.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) {
        path.clear();
        res.clear();
         vector<bool> used(nums.size(), false);
        backtracking(nums,used);
        return res;
    }
};

47. 全排列 II

本题需要进行树层去重操作，树枝去重操作逻辑：当前元素与上一层相等并且use数组的前一个为0（use[i-1]=false），表明是需要进行树层去重， 使用used数组可以将树枝去重和树层区分开来。

同时因为本题需要的是排列问题，i从0开始，为了判断一个元素是否去过，仍然可以使用used数组进行判断。

递归函数参数:used数组与传入nums

?递归终止条件:当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。

单层搜索的逻辑:排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。而used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。

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

    }


    vector<vector<int>> permuteUnique(vector<int>& nums) {
        path.clear();
        res.clear();
        vector<bool> used(nums.size(),false);
        sort(nums.begin(),nums.end());
        backtracking(nums,used);
        return res;
    }
};