题意概述

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

方法一:标记数组回溯

思路与具体做法

  • 标记数组回溯,每次遍历数组内所有元素,若当前元素未访问,则访问它(这里按序访问,即选定第几个元素),然后递归下一层,再选一个未访问过的元素访问,直到访问完所有元素
  • 到达递归边界,即访问完所有元素后,即将当前访问次序加入结果数组ans
  • 然后取消当前一层的访问标记,尝试访问别的未访问元素,遍历整个递归树
class Solution {
public:
	vector<vector<int> >ans;
    int vis[6],temp[6];
	void DFS(int u,int n,int a[],vector<int>&num,int v[]){
		if(u>n){//递归边界,将遍历过的结点加入临时数组t
			vector<int>t;
			for(int i=1;i<=n;i++){
				t.push_back(num[a[i]-1]);
			}
			ans.push_back(t);//加入ans
			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> > permute(vector<int> &num) {	
    	memset(vis,0,sizeof(vis));
        DFS(1,num.size(),temp,num,vis); 
        return ans;
    }
};

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

  • 时间复杂度:O(nn!)O(n*n!)O(nn!),字符串全排列总数共n!,而一次排列用时O(n)
  • 空间复杂度:O(n)O(n)O(n),递归深度为序列长度n

方法二:交换回溯

思路与具体做法

  • 交换回溯,递归中首先固定某一个下标对应元素,然后将其他元素进行交换。
  • 到叶子节点后返回,接着i++,u比i小1,i与其后面一个元素交换。
  • 每次从根结点到叶子结点的序列即为原序列的一个排列。 alt
class Solution {
public:
	vector<vector<int> >ans;
	void DFS(int u,int n,vector<int>&a){
		if(u>n){//递归边界,将遍历过的结点加入临时数组t
			vector<int>t;
			for(int i=1;i<=n;i++){
				t.push_back(a[i]);
			}
			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> > permute(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!logn!)O(n!logn!)O(n!logn!),字符串全排列总数为n!,而递归中嵌套了一个长度为n的循环,所以全排列时间复杂度为O(nn!)O(n*n!)O(nn!),对长为n!的ans排序了,因此应该是O(n!logn!)O(n!logn!)O(n!logn!)
  • 空间复杂度:O(1)O(1)O(1),用到常数级别的变量。