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

利用visited数组以及比较排序后数组中相邻数字的关系

回溯问题：

回溯其实就是暴力遍历 回溯是先在数组[a,b,c]中选取一个数字a 然后按照顺序或者某种关系 依次从数组中选取数字b,c 与开始选取的a组成一种排列数，这是纵向选择

那横向选择呢，假设一开始选的不是a 而是b，那是不是另一种答案呢，但是必须提前将一开始选择a的作法撤回（不选a，选b）,得到另一种结果

...

class Solution {
private:
    vector<vector<int>> result;
    vector<int> tmp;
    
     // 回溯 + 递归 
    void backtrack(vector<int> &num,vector<int> visited){
        if(tmp.size()==num.size()){
            result.push_back(tmp);
            return;
        }
        // 回溯
        // 回溯是先纵 后横
        for(int i=0;i<num.size();++i){
            if(visited[i]==1) continue;
            if(i>0 && num[i-1]==num[i] && !visited[i-1]) continue; // 同一等级  回溯之后才是
            
            visited[i]=1;
            tmp.push_back(num[i]);
            backtrack(num,visited);
            visited[i]=0;
            tmp.pop_back();
        }
 }
    
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(),num.end());
        vector<int> vistied(num.size(),0);
        
        backtrack(num,vistied);
        return result;
    }
};