力扣47:全排列Ⅱ

题目

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

思路

又是任意顺序和所有不重复的排列，显而易见我们要使用回溯的办法。
首先是回溯的结束条件即新数组的长度等于nums的长度。这道题的难点主要是如何判断当前位置已经被使用过以及当前位置是否是重复的也就是是否已经插入过了。之前的全排列Ⅰ我们使用的是bool类型的数组来判断当前位置是否被使用了，这道题同样可以使用这种方法不过想要使用这种方法我们每次都需要从头开始遍历这个bool数组从而得到一个值为false的位置。所以这次我们换一个方式我们使用过这个位置代表着什么，代表着这个位置被固定了因为他已经插入到临时数组里了它最后是要被插入到答案里的。所以我们可以定义一个变量number，这个变量代表的意思是这是第几位数字，每当我们使用过一个位置后我们就把当前位置的值和number位置的值进行交换，这样做还有一个好处就是我们不需要定义临时数组了我们直接在nums上进行交换最后长度即number等于nums的长度后直接插入nums即可。
其次就是如何解决剪枝的问题，这个问题也好解决我们在每次进入回溯函数的时候定义一个哈希表即set，在每次进入遇到一个位置时先判断它的值在set中是否能找到能找到说明它不能被固定了直接跳过到下一个位置，找不到就将该位置的值插入到set中。

代码

class Solution {
public:
    // 回溯
    void totalSort(vector<int>& nums, vector<vector<int>>& res, int number) {
        // 如果当前位置等于长度就直接插入
        if (number == nums.size()) {
            res.push_back(nums);
            return;
        }
        set<int> s;
        for (int i = number; i < nums.size(); i++) {
            // 剪枝
            // 如果在set中存在就说明是重复元素会导致答案重复
            if (s.find(nums[i]) != s.end()) {
                continue;
            }
            s.insert(nums[i]);
            // 固定使用过的值到number位置上
            swap(nums[i], nums[number]);
            totalSort(nums, res, number + 1);
            swap(nums[i], nums[number]);
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        totalSort(nums, res, 0);
        return res;
    }
};