回溯法解决 排列组合问题 全排 选排 可重复 不可重复
/* 华科机试练手 * 回溯法解决 排列组合问题 * 1 : 全排列 * 2 ：可重复全排列 * 3 : 不可重复的选择排序 * …… */#include <stdlib.h>#include <stdio.h>int solution[100];/* 可重复全排 */int Perm(int a[], int n, int level){ int i; static int sum = 0; if(level == n) { sum++; for(i=0; i<level; i++) printf("%d\t",solution[i]); printf("\n"); return; } for(i=0; i<n; i++) { if(1) { solution[level] = a[i]; Perm(a,n,level+1); } } return sum;}/* 不可重复全排 */int NoReptPerm(int a[], int n, int level){ int i,j,selected = 0; static int sum = 0; if(level == n) { sum++; for(i=0; i<level; i++) printf("%d\t",solution[i]); printf("\n"); return; } for(i=0; i<n; i++) { selected = 0; for(j=0; j<level; j++)//检查是否已经被选过 { if(solution[j] == a[i]) { selected = 1; break; } } if(!selected)//没被选过 { solution[level] = a[i];//加入解向量 NoReptPerm(a,n,level+1); } } return sum;}/* 选择排序(不可重复) */int SelectPerm(int a[], int n, int m, int level){ int i,j,selected = 0; static int sum = 0; if(level == m) { sum++; for(i=0; i<level; i++) printf("%d\t",solution[i]); printf("\n"); return; } for(i=0; i<n; i++) { selected = 0; for(j=0; j<level; j++)//检查是否已经被选过 { if(solution[j] == a[i]) { selected = 1; break; } } if(!selected)//没被选过 { solution[level] = a[i];//加入解向量 SelectPerm(a,n,m,level+1); } } return sum;}int main(int argc, char *argv[]){ int i; int a[] = {1,2,3}; i = Perm(a,3,0); printf("Total : %d\n",i); i = NoReptPerm(a,3,0); printf("Total : %d\n",i); i = SelectPerm(a,3,2,0); printf("Total : %d\n",i); return 1;}