题解 | 有重复项数字的全排列

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型vector 
     * @return int整型vector<vector<>>
     */

     void dfs(vector<vector<int>> &result,const vector<int>& num,vector<int> ¤t,vector<bool> &used)
     {
        if(current.size()==num.size())
        {
            result.push_back(current);
            return;
        }
        for(int i=0;i<num.size();i++)
        {
            if(used[i]) continue;
		  //去重关键，先排序，相邻不相等，相等continue,注意上一个未被标记
            if(i>0&&num[i]==num[i-1]&&!used[i-1]) continue;
            used[i]=true;
            current.push_back(num[i]);
            dfs(result,num,current,used);
            current.pop_back();
            used[i]=false;
            
        }
     }
    vector<vector<int> > permuteUnique(vector<int>& num) {
        // write code here
        sort(num.begin(),num.end());
        vector<vector<int>> result;
        vector<bool> used(num.size()+1,false);
        vector<int> current;
        dfs(result,num,current,used);
        return result;
    }
};