PTA—输出全排列 (20分）

递归回溯思想

题目要求：

请编写程序输出前n个正整数的全排列（n<10），并通过9个测试用例（即n从1到9）观察n逐步增大时程序的运行时间。

输入格式:

输入给出正整数n（<10）。

输出格式:

输出1到n的全排列。每种排列占一行，数字间无空格。排列的输出顺序为字典序，即序列a1,a​2,⋯,a​n排在序列b1​​ ,b2,⋯,bn之前，如果存在k使得a​1=b​1,⋯,a​k=b​k并且 a​k+1<b​k+1。

输入样例：

3

输出样例：

123

132

213

231

312

321

代码

#include<stdio.h>
int a[11]; 
int n;
int visit[11];	//记录是否“访问” 
void Find(int step)
{
	if(step==n+1)		//如果找够了，就打印 
	{
		for(int i=1;i<=n;i++)
			printf("%d",a[i]);
		printf("\n");
	}
	else
	{
		for(int i=1;i<=n;i++)
		{
			if(!visit[i])//未访问
			{
				a[step]=i;  //保存
				visit[i]=1;  //标记
				Find(step+1);	//递归寻找下一个 
				visit[i]=0;		//回溯（标记为未访问） 
			} 
		}
	}
}
int main()
{
	scanf("%d",&n);
	Find(1); //从第一个开始
 	return 0;
}