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

题目主要信息:

• 给定一组可能有重复数字的数组，输出该数组的全部排列
• 输出结果按照字典序升序排列

具体思路:

这道题类似没有重复项数字的全排列，但是因为交换位置可能会出现重复交换的情况，出现的结果需要去重，因此不便于使用交换位置的方法，我们就使用临时变量去组装一个排列的情况：每当我们选取一个数组元素以后，就确定了其位置，相当于对数组中剩下的元素进行全排列添加在该元素后面，给剩余部分进行全排列就是一个子问题，因此可以使用递归。

• 终止条件： 临时数组中选取了n个元素，已经形成了一种排列情况了，可以将其加入输出数组中。
• 返回值： 每一层给上一层返回的就是本层级在临时数组中添加的元素，递归到末尾的时候就能添加全部元素。
• 本级任务： 每一级都需要选择一个元素加入到临时数组末尾（遍历数组选择）。首先已经加入的元素不能再次加入了，因此我们需要使用额外的vis数组用于记录哪些位置的数字被加入了。同时为了去除重复元素的影响，如果当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用过了，也不需要将其纳入。

回溯的思想也与没有重复项数字的全排列类似，对于数组[1,2,2,3]，如果事先在临时数组中加入了1，后续子问题只能是[2,2,3]的全排列接在1后面，对于2开头的分支达不到，因此也需要回溯：将临时数组刚刚加入的数字pop掉，同时vis修改为没有加入，这样才能正常进入别的分支。参考下图所示：

代码实现:

class Solution {
public:
    void recursion(vector<vector<int> > &res, vector<int> &num, vector<int> &temp, vector<int> &vis){
        if(temp.size() == num.size()){ //临时数组满了加入输出
            res.push_back(temp);
            return;
        }
        for(int i = 0; i < num.size(); i++){ //遍历所有元素选取一个加入
            if(vis[i]) //如果该元素已经被加入了则不需要再加入了
                continue;
            if(i > 0 && num[i - 1] == num[i] && !vis[i - 1]) 
                continue;  //当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用过了
            vis[i] = 1;  //标记为使用过
            temp.push_back(num[i]); //加入数组
            recursion(res, num, temp, vis);
            vis[i] = 0; //回溯
            temp.pop_back();
        }
    }
    
    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(), num.end()); //先按字典序排序
        vector<int> vis(num.size(), 0); //标记每个位置的元素是否被使用过
        vector<vector<int> > res;
        vector<int> temp; 
        recursion(res, num, temp, vis); // 递归获取
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n\ast n!)O(n*n!)$，全排列的全部情况为n!，每次递归过程都是遍历数组查找元素，这里是$O(n)O(n)$
• 空间复杂度：$O(n)O(n)$，递归栈的最大深度为数组长度n，临时数组temp的空间也为$O(n)O(n)$，res属于返回必要空间