C语言回溯法 实现组合数 从N个数中选择M个数

下面是C语言回溯法实现组合数从N个数中选择M个数的完整攻略：

核心思路

回溯法是一种经典的问题求解方法，其基本思路是：从一条路径开始，依次尝试每一个分支，递归地进行尝试，直到找到解为止，而如果该路径无解，则回退到上一个路径，继续尝试其他分支。

在利用回溯法解决从N个数中选择M个数的组合数问题时，我们可以将每个数看作一个节点，根据回溯的思想依次尝试每一个节点，如果节点被选中，则进入下一层递归，否则直接回溯到上一层。在整个回溯过程中，使用一个数组记录当前已经选中的节点，当选中节点的个数等于M时，则表示已经找到了一组组合数，将其输出即可。

最后，需要注意的是，组合数并不包含顺序，即1,2,3和3,2,1是同一个组合数，因此在递归的过程中，需要对每一层的节点进行剪枝，避免重复计算。

具体实现

下面是C语言回溯法实现组合数从N个数中选择M个数的完整代码，其中n代表待选择的总数，m代表要选择的数的个数：

#include <stdio.h>

#define MAX 100

int n, m;             // 待选择的总数，要选的数的个数
int a[MAX], s[MAX];   // a数组存储所有待选择的数，s数组用于记录已选择的数

void comb(int start, int num)   //start表示待选择数的起始下标，num表示已选择的数的个数
{
    if(num == m)    // 已选择的数的个数达到要求
    {
        for(int i=0; i<m; i++)
            printf("%d ", a[s[i]]);
        printf("\n");
        return;
    }
    for(int i=start; i<n; i++)   // 枚举所有的选择
    {
        s[num] = i;   // 记录选择的下标
        comb(i+1, num+1);     // 递归进入下一层，从i+1开始，选择个数加一
    }
}
int main()
{
    printf("请输入待选择的总数和要选的数的个数：");
    scanf("%d %d", &n, &m);
    printf("请输入%d个待选择的数：\n", n);
    for(int i=0; i<n; i++)
        scanf("%d", &a[i]);
    comb(0, 0);
    return 0;
}

示例说明

假设现在有4个数：1, 2, 3, 4，从中选取2个数，即n=4, m=2，按照上面的代码进行递归，最终输出的所有组合数为：

1 2
1 3
1 4
2 3
2 4
3 4

另外，将代码中的n修改为5，m为3，输入的数分别为3, 1, 4, 7, 2，那么输出的所有组合数为：

3 1 4
3 1 7
3 1 2
3 4 7
3 4 2
3 7 2
1 4 7
1 4 2
1 7 2
4 7 2

以上就是C语言回溯法实现组合数从N个数中选择M个数的完整攻略和示例说明。