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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型vector 
     * @return int整型vector<vector<>>
     */
        void backtrack(vector<int>& num,vector<int>& temp,vector<bool>& used,vector<vector<int>>& res)
    {
        if(temp.size()==num.size())
        {
          res.push_back(temp);
          return;
        }
        for(int i=0;i<num.size();i++)
        {
            //上一个值未被使用过，说明上一次值的递归已经完成或者是正在使用上一个值，所以此时相等的值
		    //是应该要被使用的，去重去的是相等值在这次递归时已经被使用完成的值，也就是used[i-1]=false
            if(i>0&&num[i]==num[i-1]&&!used[i-1])//如果当前和上一个值相等，并且上一个值未被使用过
            {
                continue;
            }
            if(!used[i])//在当前temp里，num[i]没有被使用过
            {
                temp.push_back(num[i]);
                used[i]=true;
            }
            else
            {
                continue;
            }
            backtrack(num,temp,used,res);//递归，直到temp.size==num.size才会返回
            //递归结束以后，每往上回溯一层，used[i]记为false,temp的最后一个弹出
            temp.pop_back();
            used[i]=false;
        }
    }
    vector<vector<int> > permuteUnique(vector<int>& num) {
        // write code here
         vector<vector<int>> res;
        if(num.size()==0)
        {
            return res;
        } 
        vector<int> temp;
        vector<bool> used(num.size(),false);
        sort(num.begin(),num.end());//先排序，方便去重
        backtrack(num,temp,used,res);
        return res;
        
    }
};