题目描述
给定一个整数n,将数字1~n排成一排,将会有很多种排列方法。
现在,请你按照字典序将所有的排列方法输出。
输入格式
共一行,包含一个整数n。
输出格式
按字典序输出所有排列方案,每个方案占一行。
数据范围
1≤n≤9
样例
输入样例:
3
输出样例:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
这题依然是应用dfs,我们需要考虑到是如何查找,以及dfs需要哪些参数。考虑题目给的样例,我们容易得到有六种情况。画出三个位置,依次填上每一个数,321.可以画出树图,可以看出我们需要给dfs传递当前填到第几个数,每个位置填的是什么数,以及每个数是否被用过,第一个参数只需要用一个整形变量u,第二第三个参数则需要两个数组nums和state。我们需要按照字典序来搜索,如果当前已经填到第n+1个数,那么搜索结束,开始输出,否则查找还没用过的最小的数,填到第u个位置上,然后接着进行下一层递归搜索,然后完成这支搜索后继续循环,进行下一支搜索,但是需要注意的是,进行完一支的搜索后,填的那个数的state要恢复为未使用,因为在下一支搜索中还没有使用那个数。依照这个思路有如下代码。
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
int N=10;
int n;
void dfs(int,int[],bool[]);
int main(){
scanf("%d",&n);
int nums[N];
bool state[N]={0};
dfs(1,nums,state);
return 0;
}
void dfs(int u,int nums[],bool state[]){
int i;
if(u>n){
for(i=1;i<=n;i++)
printf("%d ",nums[i]);
putchar('\n');
}else{
for(i=1;i<=n;i++){
if(!state[i]){
nums[u]=i;
state[i]=true;
dfs(u+1,nums,state);
state[i]=false;//恢复现场
}
}
}
}