题目描述
输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
输入输出格式
输入格式：
n(1≤n≤9)
输出格式：
由1～n组成的所有不重复的数字序列，每行一个序列。每个数字保留5个常宽。
输入输出样例
输入样例#1： 复制
3
输出样例#1： 复制
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
解题思路： 1.构建一颗搜索树
以n=3为例：
n=3,就有3个数，1,2,3. 对1，画一颗搜索树如图：
红色字体表示已经数过了的数字。
其他情况同样如上，可以画出2,3的。这样对每一棵树进行深度搜索。可以找到全部结果。
2.程序实现：
2.1定义两个数组，一个b[100],存储最后的答案，一个a[100][2],用a[100][0]存储数字1-n,用a[100][1]存储该数字是否已经被搜索过了。
2.2伪代码实现：
void dfs(int k){
if(k==n){//已经从一个数字走到n个了
输出该次全排列；
retrun ;}
for(i=1->n){//n棵搜索树都应该走完
if(当前数字没有被走过){
将这颗树标记为走过；
存储到全排列数组b[k];
dfs(下一层)；
恢复标记；}
}
}
代码：
#include<iostream>
using namespace std;
int b[];
int a[][];
void dfs(int k,int n){
if(k==n+){ for(int i=;i<=n;i++){
cout<<" "<<b[i];
}
cout<<endl;
//cout<<" k: "<<k<<endl;
return;
}
for(int i=;i<=n;i++){
if(a[i][]==){
// cout<<i<<" i "<<endl;
a[i][]=;
b[k]=i;
dfs(k+,n);
a[i][]=; }
} }
int main(){
int n;
cin>>n;
for(int i=;i<=n;i++){
a[i][]=i;
a[i][]=;
}
dfs(,n); return ;
}