题意概述

• 给定一组可能重复的数字
• 要求返回改组数组的所有排列，且以数字在数组中的位置靠前为优先级，按字典序排列输出

方法一：标记数组回溯+去重

思路与具体做法

• 标记数组回溯，每次遍历数组内所有元素，若当前元素未访问，则访问它（这里按序访问，即选定第几个元素），然后递归下一层，再选一个未访问过的元素访问，直到访问完所有元素
• 到达递归边界，即访问完所有元素后，即将当前访问次序加入结果数组ans
• 然后取消当前一层的访问标记，尝试访问别的未访问元素，遍历整个递归树
• 对每次得到的访问顺序用set进行去重，如果第一次出现则加入结果数组ans
• 最后要按照字典序输出，使用sort函数对容器进行排序

class Solution {
public:
	vector<vector<int> >ans;set<string>ss;
    int vis[10],temp[10];
	void DFS(int u,int n,int a[],vector<int>&num,int v[]){
		if(u>n){//递归边界，将遍历过的结点加入临时数组t
			vector<int>t;
            string s;
			for(int i=1;i<=n;i++){
				t.push_back(num[a[i]-1]);
                s+=to_string(num[a[i]-1]);
			}
            if(ss.find(s)==ss.end()){//去重
				ss.insert(s);ans.push_back(t);
			} 
			return;
		}
		for(int i=1;i<=n;i++){//
			if(!v[i]){//核心：对选过的数字进行标记,之后不再选了 
				a[u]=i;//第u位选num数组的第i位 
				v[i]=1;
				DFS(u+1,n,a,num,v);
				v[i]=0; 
			}
		}
	}
    vector<vector<int> > permuteUnique(vector<int> &num) {	
    	sort(num.begin(),num.end());
        memset(vis,0,sizeof(vis));
        DFS(1,num.size(),temp,num,vis); 
        return ans;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O(n\ast n!)O(n*n!\; )$O(n∗n!)，对长为n的num排序了，因此应该是$O\left(n{2}_{}n\right)O(n\backslash log\_\{2\}\{n\})$O(nlog2​n),字符串全排列总数共n!,而一次排列用时O(n),所以全排列时间复杂度为$O(n\ast n!)O(n*n!)$O(n∗n!)
• 空间复杂度：$O\left(n\right)O(n)$O(n)，递归深度为序列长度n

方法二：交换回溯+去重

思路与具体做法

• 交换回溯，递归中首先固定某一个下标对应元素，然后将其他元素进行交换。
• 到叶子节点后返回，接着i++,u比i小1，i与其后面一个元素交换。
• 每次从根结点到叶子结点的序列即为原序列的一个排列。
• 对每次得到的访问顺序用set进行去重，如果第一次出现则加入结果数组ans
• 最后要按照字典序输出，使用sort函数对容器进行排序

class Solution {
public:
	vector<vector<int> >ans;
    set<string>ss;
	void DFS(int u,int n,vector<int>&a){
		if(u>n){//递归边界，将遍历过的结点加入临时数组t
			vector<int>t;
            string s;
			for(int i=1;i<=n;i++){
				t.push_back(a[i]);
                s+=a[i];
			}
            if(ss.find(s)==ss.end()){//去重
				ss.insert(s);ans.push_back(t);
			} 
			return;
		}
		for(int i=u;i<=n;i++){
			swap(a[i],a[u]);
			DFS(u+1,n,a);//核心：到叶子节点后，u比i小1，i与其后面一个元素交换 
			swap(a[i],a[u]);
		}
	}
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<int>a(7,0);
        for(int i=0;i<num.size();i++)
            a[i+1]=num[i];//所有元素往后一位
        DFS(1,num.size(),a);
        sort(ans.begin(),ans.end());
        return ans;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O(n!2_{}n!)O(n!\backslash log\_\{2\}\{n!\}\; )$O(n!log2​n!)，字符串全排列总数为n!，而递归中嵌套了一个长度为n的循环，所以全排列时间复杂度为O(n*n!)，对长为n!的ans排序了，因此应该是$O(n!logn!)O(n!logn!)$O(n!logn!)
• 空间复杂度：$O(n!)O(n!)$O(n!)，用到了一个大小为n!的set容器及数组。