排列组合子集相关方法的整理

子集

没有重复数字的子集
没有重复数字的子集表示子集集合中不会产生重复，即对于数组中的每一个数字，都有选和不选的两种决策，直接DFS对决策进行暴力搜索，每次都对选和不选进行决策，代码非常简单。

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> t;

    void dfs(const vector<int>& nums, int idx){
        if(idx == nums.size()){
            ans.push_back(vector<int>(t));
            return;
        }
        //选
        t.push_back(nums[idx]);
        dfs(nums, idx + 1);
        t.pop_back();
        //不选
        dfs(nums, idx + 1);

    }

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return ans;
    }
};

子集II

有重复数字的子集
有重复数字的子集再跟上面一样暴力搜索就会产生重复，如果使用和上面相似的代码，则需要产生大量的判断。这里采用一种全新的判断方法求子集。使用for循环引入遍历顺序，并对每一个遍历层次进行判断去除重复。

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> t;
    int len;
    void dfs(const vector<int>& nums, int sidx){
        ans.push_back(vector<int>(t));
        //不同的sidx即代表不同的层次，一下判断每个重复字符只在同一个sidx层次中出现一次
        for(int i = sidx; i < len; ++i){
            if(i && nums[i - 1] == nums[i] && i != sidx)    continue;   //此句为去除重复语句
            t.push_back(nums[i]);
            dfs(nums, i + 1);
            t.pop_back();
            //这里不用再向下搜索不选的情况，因为for循环的向下已经代表了不选的情况
            //如果这里搜索不选的情况则会产生重复
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        len = nums.size();
        sort(nums.begin(), nums.end());
        dfs(nums, 0);
        return ans;
    }
};

组合

组合
采用与子集II相同的搜索方法。

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> t;
    vector<int> nums;
    int ck;
    int len;

    void dfs(int idx){
        if(t.size() == ck){
            ans.push_back(vector<int>(t));
            return;
        }

        for(int i = idx; i < len; ++i){
            t.push_back(nums[i]);
            dfs(i + 1);
            t.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) {
        ck = k, len = n;
        for(int i = 1; i <= n; ++i){
            nums.push_back(i);
        }
        dfs(0);
        return ans;
    }
};

全排列

不含重复数字的全排列
用for循环的方法寻找全排列，不同于组合，排序是有顺序的，因此不用start——index，直接从头开始for循环就行了，使用visited表示选择，一次选择的结束（即for循环自增到下一个元素）天然表示不选择。

class Solution {
public:
    const static int N = 10;
    bool visited[N] = {0};
    vector<vector<int>> ans;
    vector<int> t;

    void dfs(const vector<int>& nums){
        if(t.size() == nums.size()){
            ans.push_back(vector<int>(t));
            return;
        }
        for(int i = 0; i < nums.size(); ++i){
            if(visited[i]) continue;
            visited[i] = true;
            t.push_back(nums[i]);
            dfs(nums);
            t.pop_back();
            visited[i] = false;
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums);
        return ans;
    }
};

全排列II

含有全部数字的全排列
含有重复数字的重排列核心问题是消去重复，而这类问题的消去重复往往要想到组合中的nums[i - 1] == nums[i]方法，这里只需要出现一次，即连续相同数字的前一个没访问过的时候，都不准访问，每个连续的相同数字都符合这一规则，就会产生第一个字母不访问的时候，后续的都无法访问，即达到了去重的效果。

class Solution {
public:
    const static int N = 10;
    bool visited[N] = {0};
    vector<vector<int>> ans;
    vector<int> t;

    void dfs(const vector<int>& nums){
        if(t.size() == nums.size()){
            ans.push_back(vector<int>(t));
            return;
        }

        for(int i = 0; i < nums.size(); ++i){
            if(visited[i])  continue;
            if(i && nums[i - 1] == nums[i] && !visited[i - 1])  continue;
            visited[i] = true;
            t.push_back(nums[i]);
            dfs(nums);
            t.pop_back();
            visited[i] = false;
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        dfs(nums);
        return ans;
    }
};