回溯法解决 排列组合问题 全排 选排 可重复 不可重复

/* 华科机试练手 * 回溯法解决 排列组合问题 * 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;}