C语言 回溯法 全排列

题目：输出自然数 11 到 nn 所有不重复的排列，即 nn 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

题解1：

#include
int visit[10],n,line[20]; //visit是标记是否使用过该数字，n是输入，line存储结果

void print(){ //单独的输出函数
 for(int i=1;i<=n;i++){ //输出n个数的全排列结果
  printf("%d ",line[i]);
 }
 printf("n");
}

void dfs(int num){ //num代表的是现在正在排列第n位数
 if(num==n+1){ //只有n+1时，才是排列结束的结果
  print();
  return;
 }
 for(int i=1;i<=n;i++){ //分别尝试范围内的数是否满足条件
  if(visit[i]==0){ //需判断的条件：数字没有被使用过
   line[num]=i; //存储排列结果
   visit[i]=1; //标记此数字已使用
   dfs(num+1); //dfs深搜 
   visit[i]=0; //标记此数字未使用
  }
 }
}

int main(){ 
 scanf("%d",&n);
 dfs(1);
 return 0;
}

链接参考：http://t.csdn.cn/c66Zs 

题解2：

#include

int a[10]={1,2,3,4,5,6,7,8,9,10};
void swap(int a[],int m,int n){
 int k=a[m];
 a[m]=a[n];
 a[n]=k;
}
void allsort(int a[],int k,int m){
 if(k==m){//如果待全排列数组，起始等于末尾，说明已经产生了一种结果，进行输出
  for(int i=0;i<=k;i++){
   printf("%d ",a[i]);
  }
  printf("n");
 }
 else{
  for(int i=k;i<=m;i++){
   swap(a,i,k);//交换当前元素与i位置的元素
   allsort(a,k+1,m);//对当前元素之后的元素进行全排列
   swap(a,i,k);//回溯
  }
 }
}
int main(){
 int b;
 scanf("%d",&b);
 allsort(a,0,b);
 return 0;
} 

链接参考：