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

有重复项数字的所有排列
题解一：搜索回溯
题解思路： 该题与“没有重复项数字的所有排列“思路一样，只是多了约束条件。
约束条件：
 1.一个数字不能重复地被选择。
 2.不能产生重复地排列。 所以排列中地同一个位置不能出现相同的。
图示：

剪枝：
使用一个vis数组标记使用过的数字，如果使用过了就回溯。
如果当前的选项num[i],与同一层的前一个选项num[i-1]相同且num[i-1]已经使用了，那表示同一层是相同的数字

复杂度分析：
 时间复杂度：，同无重复一样，最坏情况就是数组无重复
 空间复杂度：，N为序列的长度。除返回的数组以外，递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，这里可知递归调用深度为 。

实现如下：

class Solution {
public:
    vector<vector<int> >ans;
    void dfs(vector<int>& num,vector<int>&vis,vector<int> tmp){
        if(tmp.size()== num.size()){ans.emplace_back(tmp);return;}  //表明找到一个排列
        for(int i = 0;i<num.size();++i){
            if(vis[i] == 1) continue;  //如果已经使用
            if(i>0 && num[i-1] == num[i] && !vis[i-1]) continue;  //当前的选项num[i],与同一层的前一个选项num[i-1]相同且num[i-1]已经使用了
                vis[i] = 1;  //标记使用过
                tmp.emplace_back(num[i]); //加入数组
                dfs(num,vis,tmp);
                //回溯
                vis[i] = 0;
                tmp.pop_back();
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<int> vis(num.size(),0);
        sort(num.begin(),num.end());
        dfs(num,vis,vector<int>());
        return ans;
    }
};

题解二：使用set去重
利用set不能有重复元素的特性来去除重复排列。
复杂度分析：
 时间复杂度：同无重复一样，最坏情况就是数组无重复，对vector插入set的时间复杂度为logN，所以时间复杂度为O(N!*NlogN)
 空间复杂度：,最坏的情况下，没有重复项，set中需要存N乘以每一种排列的个数(N!)
实现如下：

class Solution {
public:
    vector<vector<int> >ans;
    int vis1[1001];
    set<vector<int>> pai;
    void dfs(vector<int>&num,int cur,vector<int>& tt){
        if(cur == num.size()) {pai.insert(tt); return;}  //找到一个排列
        for(int i = 0;i<num.size();i++){
            if(vis1[i]==0){
                vis1[i]=1;
                tt.emplace_back(num[i]);  
                dfs(num, cur+1, tt);    
                //回溯
                vis1[i] = 0;
                tt.pop_back();
            }
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<int> tt;
        dfs(num,0,tt);
        for(auto it:pai) ans.push_back(it);  //从set拷贝到vector
        return ans;
    }
};