1、思路

• 思路与上一题【剑指 Offer II 083. 没有重复元素集合的全排列】基本一致 ，只不过在DFS处理全排列的过程中（for循环内）需要用一个Set集合来存放已经交换过的重复元素，即不让当前的nums[i]与一个等值的已经交换过的元素再进行交换;

• 例如：对[2，1，1]操作，只会将2与第一个1进行交换，不会与第二个1交换。因为第一个元素与第二个元素交换后变成[1，2，1]，进入下一层递归会得到[1，2，1]与[1，1，2]两种结果，加上原本的排列共有三种，刚好符合答案。

• 用unordered_set也可以，但会消耗更多内存，因为散列表为了实现 $O(1)$ 时间复杂度的查找，会开得比所需空间要大，而set底层是红黑树，需要多大的空间就占用多大，不过查找效率是 $O(logN)$ 。

2、代码

class Solution {
public:
    void dfs(vector<int>& nums, int i, vector<vector<int>>& res)
    {
        if (i == nums.size())
        {
            res.push_back(nums);
            return;
        }

        set<int> Set;
        for (int j = i; j < nums.size(); ++ j)
        {
            if (Set.find(nums[j]) == Set.end()) //对集合内不存在的元素才进行递归
            {
                Set.insert(nums[j]);            //当前元素插入集合中

                swap(nums[i], nums[j]);
                dfs(nums, i + 1, res);
                swap(nums[i], nums[j]);
            }
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;

        dfs(nums, 0, res);

        return res;
    }
};