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

回溯法，求排列的问题在回溯函数中需要用到used标记数组，同时还需要进行去重。去重的方法有两种，一种是在递归返回条件的地方，判断结果集中是否已存在path；另一种是在回溯是判断，对于一排序的序列num，如果后面的元素与前面的元素重复，则只使用前面的第一个元素。

class Solution {
public:
    void backtrack(const vector<int>& num,vector<bool>& used,vector<vector<int>>& result,vector<int>& path){
        if(path.size()==num.size()){
            if(!count(result.begin(),result.end(),path)) result.push_back(path);
        }
        for(int i=0;i<num.size();i++){
            //if(i > 0 && num[i] == num[i - 1] && used[i - 1] == false) continue;
            if(!used[i]){
                used[i]=true;
                path.push_back(num[i]);
                backtrack(num, used, result, path);
                path.pop_back();
                used[i]=false;
            }
            else continue;
        }
    }
    
    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(),num.end());
        int n=num.size();
        vector<vector<int>> result{};
        vector<int> path{};
        vector<bool> used(n, false);
        backtrack(num, used, result, path);
        return result;
    }
};