题目描述
输出自然数 11 到 nn 所有不重复的排列，即 nn 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
输入格式
一个整数 nn。
输出格式
由 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 <=9
本题方法有多种。
STL方法: #include 里有一个函数叫全排列函数
next_permutation
俺管他叫字典排函数，
与本题正好吻合上，于是你瞬间觉得水题一道；
奉上AC代码：
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
int a[10];
using namespace std;
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
a[i]=i;
for(int i=1;i<=n;i++)
printf("%5d",a[i]);
printf("\n");
while(next_permutation(a+1,a+1+n))
{
for(int i=1;i<=n;i++)
printf("%5d",a[i]);
printf("\n");
}
return 0;
}
STL大法好呀！！！
DFS方法：DFS，对楼上的回溯+剪枝进行详解。
我们以N=3为例，构造一棵搜索树（或说是状态树）来进行搜索。
同时构造出三个格子，用来存放搜索树中的结果。
现在，我们从第一格开始搜索。第一格填1的搜索树如下：
所以N=3的情况下，第一格填1的排列情况共有两种123,132.
第一格填2的搜索树如下：
所以N=3的情况下，第一格填2的排列情况共有两种 213,231.
如果你看懂了，请你自己画画第一格填3的搜索树。
程序实现
我们总结一下在上一部分中的思路在程序中如何实现。
先定义两个数组，一个是用来存放解的，一个是用来标记该数是否用过。
我们可以先写一个用于打印的函数print()，每当深搜时找到一个符合条件的解时，则print()一下，输出这个解（注意题目输出要求）。
接下来就是写深搜的函数了。主要思路：先判断格子是否填满了，如果填满，则print()一下。
如果没有填满，则开始循环，在循环中先判断当前填的数是否用过，如果没有，则填入，搜索下一格。
程序实现如下：
#include<bits/stdc++.h>
using namespace std;
int n,pd[100],used[100];//pd是判断是否用过这个数
void print()//输出函数
{
int i;
for(i=1;i<=n;i++)
printf("%5d",used[i]);//保留五位常宽
cout<<endl;
}
void dfs(int k)//深搜函数，当前是第k格
{
int i;
if(k==n) //填满了的时候
{
print();//输出当前解
return;
}
for(i=1;i<=n;i++)//1-n循环填数
{
if(!pd[i])//如果当前数没有用过
{
pd[i]=1;//标记一下
used[k+1]=i;//把这个数填入数组
dfs(k+1);//填下一个
pd[i]=0;//回溯
}
}
}
int main()
{
cin>>n;
dfs(0);//注意，这里是从第0格开始的！
return 0;
}
还有一大堆方法哈！！！！
本弱狗就讲到这里啦！！！
