47、全排列II

参考链接：https://blog.csdn.net/SHAOYEZUIZUISHAUI/article/details/105998978

---

 利用set去除重复

class Solution {
    vector<vector<int>>res;
    vector<bool>used;
    void generate_permute(vector<int>&nums,vector<int>&p)
    {
        if(p.size()==nums.size())
        {
            res.push_back(p);
            return;
        }
        for(int i=0;i<nums.size();i++)
        {
            if(used[i]==false)
            {
                p.push_back(nums[i]);
                used[i]=true;
                generate_permute(nums,p);
                p.pop_back();
                used[i]=false;
            }
        }
    }

public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {

        vector<int>p;
        if(nums.size()==0)return res;
        //false 表示还没有访问过，true  表示已经访问过
        used=vector<bool>(nums.size(),false);
        generate_permute(nums,p);
        //用set处理最后的重复元素
        set<vector<int>>tmp(res.begin(),res.end());
        res.clear();
        for(auto i:tmp)
        {
            res.push_back(i);
        }
        return res;
    }
};

---

先排序，再比较前后是否重复

class Solution {
    vector<vector<int>>res;
    vector<bool>used;
    void generate_permute(vector<int>&nums,vector<int>&p)
    {
        if(p.size()==nums.size())
        {
            res.push_back(p);
            return;
        }
        for(int i=0;i<nums.size();i++)
        {
            if(used[i]==false)
            {
                //比较前后两个是否重复，且前一个重复的元素是出于待访问状态，因为类似的操作已经在前面经历过了，经历一次就好
                if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false)
                    continue;
                p.push_back(nums[i]);
                used[i]=true;
                generate_permute(nums,p);
                p.pop_back();
                used[i]=false;
            }
        }
    }

public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {

        vector<int>p;
        if(nums.size()==0)return res;
        //false 表示还没有访问过，true  表示已经访问过
        used=vector<bool>(nums.size(),false);
        //因为有重复的部分，保持输出不重复，先排序，比较前后两个是否重复
        sort(nums.begin(),nums.end());
        generate_permute(nums,p);

        return res;
    }
};