题意概述

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

方法一：标记数组回溯

思路与具体做法

• 标记数组回溯，每次遍历数组内所有元素，若当前元素未访问，则访问它（这里按序访问，即选定第几个元素），然后递归下一层，再选一个未访问过的元素访问，直到访问完所有元素
• 到达递归边界，即访问完所有元素后，即将当前访问次序加入结果数组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(n\ast n!)O(n*n!)$O(n∗n!)，字符串全排列总数共n!,而一次排列用时O(n)
• 空间复杂度：$O\left(n\right)O(n)$O(n)，递归深度为序列长度n

方法二：交换回溯

思路与具体做法

• 交换回溯，递归中首先固定某一个下标对应元素，然后将其他元素进行交换。
• 到叶子节点后返回，接着i++,u比i小1，i与其后面一个元素交换。
• 每次从根结点到叶子结点的序列即为原序列的一个排列。

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(n\ast n!)O(n*n!)$O(n∗n!)，对长为n!的ans排序了，因此应该是$O(n!logn!)O(n!logn!)$O(n!logn!)
• 空间复杂度：$O\left(1\right)O(1)$O(1)，用到常数级别的变量。