代码随想Day29 | 491.递增子序列、46.全排列、47.全排列 II

491.递增子序列?

本题和 90.子集II?非常像，但又很不一样，很容易掉坑里。 这道题需要考虑的点有：

如何去除同一层已经使用过某数的情况：需要在某一层使用哈希表，来记录状态，实现去重，因为题中规定了数的范围，也可以用数组代替哈希表，效率更高；

如何判断某个子序列要继续向下递归：两种情况 1.子序列的最后一个值小于等于当前节点；2. 当前节点在这一层没有被使用过；

详细代码如下：

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    void backtrack(vector<int> nums, int index)
    {
        if(path.size()>1) res.push_back(path); //大于1就能添加到结果集
        if(index==nums.size()) return ;
        int used[201]={0}; //局部变量，用来去重，记录当前层是否用过某一个树
        for(int i=index;i<nums.size();i++)
        {
            if(!path.empty()&&path.back()>nums[i]||used[nums[i]+100]==1) continue;
            used[nums[i]+100]=1;
            path.push_back(nums[i]);
            backtrack(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtrack(nums,0);
        return res;
    }
};

46.全排列?

本题重点感受一下，排列问题?与?组合问题，组合总和，子集问题的区别。?排列问题不能用?startIndex，因为取到后面的索引之后还可以再取前面的值，因此排列问题需要一个used数组来记录某个元素是否用过，用过时continue，否则进入下一个循环。详细代码如下：

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    void backTrack(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]);
            backTrack(nums,used);
            path.pop_back();
            used[i]=false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(),false);
        backTrack(nums,used);
        return res;
    }
};

47.全排列?II?

本题?就是我们讲过的?40.组合总和II?去重逻辑?和?46.全排列?的结合，这里需要注意一下去重的思路，树层去重比较高效，used[i-1]=false对应的是树层去重，详细代码如下：

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    void backtrack(vector<int>nums, vector<bool>& used)
    {
        if(nums.size()==path.size())
        {
            res.push_back(path);
            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; //当前值取过了不能再取
            used[i]=true;
            path.push_back(nums[i]); 
            backtrack(nums,used);
            path.pop_back();
            used[i]=false;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<bool> used(nums.size(),false);
        sort(nums.begin(),nums.end());
        backtrack(nums,used);
        return res;
    }
};