全排列问题

题目描述

输出自然数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 #include<bits/stdc++.h> 
 2 using namespace std;
 3 int n;
 4 int ans[15];//保存当前的方案
 5 int use[15];//表示每个数是否被用过
 6 void dfs(int x){//X表示当前搜索到那个数
 7     if(x>n){//如果N位都搜索完了，就输出方案并返回
 8         for(int i=1;i<=n;i++)
 9             printf("% 5d",ans[i]);//输出方案 
10         puts("");
11         return;
12     }
13     for(int i=1;i<=n;i++)//从小到大枚举
14     if(!use[i]){//判断这个数是否用过
15         ans[x]=i;//保存到方案中
16         use[i]=1;//标记这个数被使用了
17         dfs(x+1);//进行下一步搜索
18         use[i]=0;//撤销标记
19     }
20 }
21 int main()
22 {
23 
24     scanf("%d",&n);//输入
25     dfs(1);//从第一个数开始搜索；
26 }