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

#include <algorithm>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型vector 
     * @return int整型vector<vector<>>
     */
    static bool compare_int(int a, int b){
        return a<b;
    }
    static bool compare_vectorint(vector<int>a , vector<int>b){
            bool flag=true;
            for (int i=0; i<a.size(); i++) {
                if (a[i]!=b[i]) {
                    a[i]<b[i]?flag=true:flag=false;
                    break;
                }
            }
            return flag;
    }
    vector<vector<int>>result;
    vector<int>path;
    vector<vector<int>> permuteUnique(vector<int>& num) {
        // write code here
        if (num.size()==0||num.size()==1) {
            result.push_back(num);
            return result;
        }
        sort(num.begin(), num.end(),compare_int);
        vector<int>used(num.size(),0);
        BackTracking(num, used);
        sort(result.begin(), result.end(), compare_vectorint);
        return result;
    }

    void BackTracking(vector<int>& num, vector<int>& used){
        if (path.size()==num.size()) {
            result.push_back(path);
            return;
        }
        for (int i=0; i<num.size(); i++) {
            //横向树层剪枝
            if (i>0&&num[i]==num[i-1]&&used[i-1]==0) {
                continue;
            }
            //防止反复取某一个数
            else if (used[i]==1) {
                continue;
            }
            else {
                path.push_back(num[i]);
                used[i]=1;
                BackTracking(num, used);
                path.pop_back();
                used[i]=0;
            }
        }
    }
};