7-2 输出全排列（20 分）（dfs）

7-2 输出全排列（20 分）

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

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

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

#include<stdio.h> #include<stdlib.h> #include<string.h> int vis[30],n; int shu[9]= {1,2,3,4,5,6,7,8,9}; int ans[10],k,x; void dfs(int n,int len) { int i; if(len == n) { for(i=0; i<n-1; i++) printf("%d ",ans[i]); printf("%d\n",ans[n-1]); } for(i=1; i<=n; i++) { if(!vis[i]) { ans[len++] = i; vis[i] = 1; dfs(n,len); vis[i] = 0; len --; } } } int main() { scanf("%d",&n); dfs(n,0); return 0; }