题目主要信息:

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

具体思路:

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

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

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

alt

代码实现:

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(nn!)O(n*n!),全排列的全部情况为n!,每次递归过程都是遍历数组查找元素,这里是O(n)O(n)
  • 空间复杂度:O(n)O(n),递归栈的最大深度为数组长度n,临时数组temp的空间也为O(n)O(n),res属于返回必要空间