组合：数字型

【问题】利用递归方法找出从自然数1,2,…,n中任取r个数的所有组合
【例如】n=5,r=3，所有组合为：
组合 - 图1

方法一

【思路】

抽象问题：1,…,n中选r —> f(n,r)
从边界n考虑，n要么取，要么不取 —> f(n,r) = f(n-1, r) + f(n-1, r-1)
退出条件：r==0时，就已经选完了

异常条件：n<r的时候

int a[50]; //存放组合的结果数组
void f(int n,int r,int m) {
 // 从1,...n序列中选r个数字进行组合，当前已选m个数
 // 【m理解】当前已选择m个数 or 此次选择的数放到a[m]的位置 or 结果数组的最后一位
 int i;
 if (n<r) return ; //异常条件
 if (r==0) { //从1,...,n序列中选0个数字进行组合
     // 打印输出此次组合的结果
     for (i=0; i<m; i++) printf("%d", a[i]);
     printf("\n");
 } else {
     // 将n选入数组，赋值到结果数组
     a[m] = n;
     f(n-1, r-1, m+1); //已经选了n这个数字-->从1,...,n-1选r-1个
     //不选n
     f(n-1, r, m); //n没有选-->从1,...,n-1选r个
 }
}

方法二

【代码】

// 从1-n的数字中选r个数字
//    目前选的一个放入a[m]位置中
void C(int n, int r, int a[], int m) {
    int i;
    if (r==0) { //选完了
        //输出
        for (i=0; i<m; i++) printf("%d", a[i]);
        printf("\n");
    } else {
        // 在[r,n]的范围内选一个数字放入a[m]
        for (i=n; i>=r; i--) {
            a[m] = i;
            C(i-1, r-1, a, m+1);
        }
    }
}

【理解】用树状的形式输出递归树（先序）
树状的方式类似于这种https://blog.csdn.net/summer_dew/article/details/82937941
组合 - 图2

完整代码

方法一：

#include<stdio.h>

int a[50];

void f(int n,int r,int m) {
    int i;

    if (n<r) return ;

    if (r==0) {
        for (i=0; i<m; i++) printf("%d", a[i]);
        printf("\n");
    } else {
        //选n
        a[m] = n;
        f(n-1, r-1, m+1);
        //不选n
        f(n-1, r, m);
    }
}

int main() {
    int n,r;
    while (1) {
        printf("输入n与r，空格分割\n>>> ");
        scanf("%d%d", &n, &r);
        f(n, r, 0);
        printf("\n");
    }
    return 0;
}

方法二：

#include<stdio.h>

// 从1-n的数字中选r个数字
//    目前选的一个放入a[m]位置中
void C(int n, int r, int a[], int m) {
    int i;

    // 以树状输出递归树
    /*
    for (i=0; i<m; i++) {
        printf("  ");
    }
    printf( "C(%d,%d, '" , n,r);
    for (i=0; i<m; i++) {
        printf("%d ", a[i]);
    }
    printf("', %d)",m );
    printf("\n");
    */

    if (r==0) { // 选完了
        // 输出
        for (i=0; i<m; i++) printf("%d", a[i]);
        printf("\n");
    } else {
        // 在[r,n]的范围内选一个数字放入a[m]
        for (i=n; i>=r; i--) {
            a[m] = i;
            C(i-1, r-1, a, m+1);
        }
    }
}

int main() {
    int n,r;
    int a[50];
    while (1) {
        printf("输入n与r，空格分割\n>>> ");
        scanf("%d%d", &n, &r);
        C(n, r, a, 0);
        printf("\n");
    }
    return 0;
}

组合：字符型

【问题】从长度为n个字符串str中选出m个元素的可能
【思路】
组合 - 图3

【代码】

char *tmp;    //中间结果
int top;
int count;    //种数
//递归求组合数
void combination(char *str, int n, int m )
{
    if( n < m || m == 0 )    return ;        //case 1：不符合条件，返回
    combination( str+1, n-1, m );            //case 2：不包含当前元素的所有的组合
    tmp[ top++ ] = str[0];                    //case 3：包含当前元素
    if( m == 1 ){                                //case 3.1：截止到当前元素
        printA( tmp, top );
        printf("\n");
        count++;
        top--;
        return;
    }
    combination( str+1, n-1, m-1);                //case 3.2：包含当前元素但尚未截止
    top--;                                //返回前恢复top值
}

【理解】将递归树进行先序输出
树状的方式类似于这种https://blog.csdn.net/summer_dew/article/details/82937941
组合 - 图4

【完整代码】

#include<stdio.h>
#include<stdlib.h>

char *tmp;    //中间结果
int top;    //
int count;    //种数

//打印长度为n的数组元素
void printA(char *str,int n)
{
    int i;
    for(i=0;i<n;i++){
        printf("%c ",str[i]);
    }
}

//递归求组合数
void combination(char *str, int n, int m )
{
    if( n < m || m == 0 )    return ;        //case 1：不符合条件，返回
    combination( str+1, n-1, m );            //case 2：不包含当前元素的所有的组合
    tmp[ top++ ] = str[0];                    //case 3：包含当前元素
    if( m == 1 ){                            //case 3.1：截止到当前元素
        printA( tmp, top );
        printf("\n");
        count++;
        top--;
        return;
    }
    combination( str+1, n-1, m-1);        //case 3.2：包含当前元素但尚未截止
    top--;                                        //返回前恢复top值
}

int main()
{

    int n,m;//存放数据的数组，及n和m
    char *str;
    printf("输入n与m，用空格隔开\n>>> ");
    scanf("%d%d",&n,&m);

    str = (char *) malloc( sizeof(char) * n );
    tmp = (char *) malloc( sizeof(char) * m );

    printf("输入字符串\n>>> ");
    scanf("%s", str);

    printf("\n%s %d中选取%d个", str, n, m);
    combination( str, n, m );//求数组中所有数的组合
    printf("总数%d\n", count);

    //记得释放malloc申请来的资源
    free(str);
    free(tmp);

    return 0;
}