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

#include <unordered_set>
#include <vector>
class Solution {
public:
    void dfs(vector<vector<int>> & ans, vector<bool> vis, vector<int> temp, vector<int> num, int n){
        if(n == temp.size()){//退出窗口
            ans.push_back(temp);
        }

        for(int i = 0; i < n; i++){
            if(vis[i]) continue;
            if(i > 0 && num[i] == num[i - 1] && !vis[i - 1]) continue;//这里的!vis[i - 1]是最关键的，如果前一个位置未访问并且与前一个数相等，则表示这种情况有重复，而当vis[i - 1]为真表示，当前元素并不是主要元素
            temp.push_back(num[i]);
            vis[i]  = true;
            dfs(ans, vis, temp, num, n); //相当于往下走，进行更小型数组的递归
            //本层分支，其他情况的的处理，也就是回溯
            vis[i] = false;
            temp.pop_back();
        }
    }
    vector<vector<int> > permuteUnique(vector<int>& num) {
            sort(num.begin(), num.end());
            int n = num.size();
            vector<vector<int>> ans;
            vector<int> temp;
            if(n == 0) return ans;
            vector<bool> vis(n, false);
            dfs(ans, vis, temp, num, n);

            return ans;
       
    }
};