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

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> temp;
    vector<int> used;
    vector<vector<int> > permuteUnique(vector<int>& num) { 
        sort(num.begin(), num.end());
        used = vector<int>(num.size(), 0);

        dp(num);

        return ans;
    }

    void dp(vector<int> &num){  
        //通过选取的方式，temp凑齐了个数既组织完毕一个情况，每一层既管理一位上取什么数；因为下层是下一位，取得数应该从头开始估量，
        //若数取过了，跳过；对于重复数，如果重复数使用了，说明上一层用的，这一层任然可以使用（不同位）；
        //如果前一个重复数没有使用，则表示这一位重复书已经在同一位上使用过了，不能例举同一位的相同数
        if(temp.size() == num.size()){
            ans.push_back(temp);
            return;
        }

        for(int i=0; i<num.size(); ++i){   //排列，从0开始；
            if(used[i])continue;

            if(i>0 && num[i]==num[i-1] && !used[i-1])continue;

            temp.push_back(num[i]);
            used[i] = 1;
            dp(num);
            temp.pop_back();
            used[i] = 0;
        }
    }
};