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

class Solution {
public:
    //本题依然是排列问题，但是和上一题的区别就在于本题可以有重复的元素
    //那么就牵扯到一个问题：去重，其实去重的原理也很简单，只要和上一个元素相同直接跳即可
    //为了标记数组每个位置的值是否被使用过，定义一个used数组来确保
    vector<vector<int> >res;
    vector<int> path;
    bool used[10];//题目中说了n<=8所以开10 个大小的空间足够了
    void process(vector<int> num,bool used[]){
        //base case
        //当path的大小==num的大小时返回
        if(path.size()==num.size()){
            res.push_back(path);
            return;
        }
        for(int i=0;i<num.size();i++){
            //去重
            if((i!=0&&num[i]==num[i-1]&&used[i-1]==true)||!used[i]){//说明重复了，直接跳过或者是这个位置的值已经被选过了。
                continue;
            }
            else{
                used[i]=false;
                path.push_back(num[i]);
                process(num, used);//递归
                //回溯
                used[i]=true;
                path.pop_back();
            }
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
        for(int i=0;i<10;i++)
            used[i]=true;
        if(num.size()<=0)
            return res;
        sort(num.begin(),num.end());
        process(num,used);
        return res;
    }
};