题解 | #有重复项数字的所有排列# 11-3 05 回溯去重，记下来

// 回溯
class Solution {
public:
    vector<vector<int>> res;
    
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> temp;
        
        vector<bool> visited(nums.size(), false);  // 标记访问
        DFS(temp, nums, visited);
        return res;
    }
    void DFS(vector<int>& temp, vector<int>& nums, vector<bool>& visited)
    {
        if(temp.size() == nums.size()) {
            res.push_back(temp);
            return;
        }
        
        for(int i = 0; i < nums.size(); ++i) {
            if(visited[i])  {
                continue;
            }
            // 去重
            if(i != 0 && nums[i] == nums[i-1] && !visited[i - 1])  {
                continue;
            }
            
            visited[i] = true;
            temp.push_back(nums[i]);
            DFS(temp, nums, visited);
            temp.pop_back();
            
            visited[i] = false;   // 回溯
        }
    }
};