代码随想录算法训练营29期Day29|LeetCode 491,46,47

文档讲解：递增子序列全排列全排列II

491.递增子序列

题目链接：https://leetcode.cn/problems/non-decreasing-subsequences/description/

思路：

首先我们开一个vector作为子序列数组。在搜索的每一层中，我们枚举nums数组中的每一个数字，判断是否大于等于vector中的最后一个数，如果是，则加入，然后进入下层搜索，如果不是，则接着枚举。同时为了去重，我们在每层循环中开一个bool数组，记录前面出现的数字。如果枚举到的数字出现过，直接跳过即可。

核心代码：

class Solution {
private:
    vector<vector<int>> ans;
    vector<int> rec;
    void dfs(vector<int>& nums,int x){
        if(rec.size()>1) ans.push_back(rec);   
        bool flag[205];
        memset(flag,false,sizeof(flag));
        for(int i=x;i<nums.size();i++){
            if(nums[i]>=rec.back()&&!flag[nums[i]+100]){
                rec.push_back(nums[i]);
                dfs(nums,i+1);
                rec.pop_back();
                flag[nums[i]+100]=true;
            }
        }
        return;
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        bool flag[205];
        memset(flag,false,sizeof(flag));
        for(int i=0;i<nums.size()-1;i++){
            if(flag[nums[i]+100]) continue;
            flag[nums[i]+100]=true;
            rec.push_back(nums[i]);
            dfs(nums,i+1);
            rec.pop_back();
        }
        return ans;
    }
};

46.全排列

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

思路：

本题很简单。假设nums数组大小为n。每层搜索枚举一个当前位置的数，搜索到第n+1层时一个排列就完成了，将当前排列加入答案即可。当所有搜索完成后，全排列就完成了。

注意每层搜索有可能枚举相同位置的数，因此要开一个全局的bool数组作为标识，记录某位置是否被使用过，如果没被使用过，标记其被使用，加入排列进入下层循环。如果已经被使用了，跳过即可。

注意回溯时要取消标记，将加入排列的数退出。

核心代码：

class Solution {
private:
    bool flag[10];
    vector<vector<int>> ans;
    vector<int> path;
    void dfs(vector<int>& nums,int x){
        if(x==nums.size()){
            ans.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(flag[i]) continue;
            path.push_back(nums[i]);
            flag[i]=true;
            dfs(nums,x+1);
            path.pop_back();
            flag[i]=false;
        }
        return;
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        memset(flag,false,sizeof(flag));
        dfs(nums,0);
        return ans;
    }
};

47.全排列II

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

思路：

本题与上道题目几乎一致。唯一需要注意的有两点：

1.每层搜索不能使用前面层搜索过的相同位置的数。

2.每层搜索内不能使用相同大小的数，因为当前位置使用相同的数产生的是相同的排列。

第一点上一题解决了，不再赘述。第二点需要我们在循环内开一个bool数组进行标记。枚举每个数都要进行判断，没被用过就可以用，然后打上标记。用过了则跳过即可。

核心代码：

class Solution {
private:
    bool flag[10];
    vector<vector<int>> ans;
    vector<int> path;
    void dfs(vector<int>& nums,int x){
        if(x==nums.size()){
            ans.push_back(path);
            return;
        }
        bool book[25];
        memset(book,false,sizeof(book));
        for(int i=0;i<nums.size();i++){
            if(flag[i]||book[nums[i]+10]) continue;
            book[nums[i]+10]=true;
            path.push_back(nums[i]);
            flag[i]=true;
            dfs(nums,x+1);
            path.pop_back();
            flag[i]=false;
        }
        return;
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        memset(flag,false,sizeof(flag));
        dfs(nums,0);
        return ans;
    }
};