C++中求组合数的四种算法实现与对比

问题定义与目标

组合问题的核心目标是找出从自然数 1、2、... 、n 中任取 r 个数的所有不重复组合。例如当 n=5，r=3 时，需要输出如 (1,2,3)、(1,2,4) 等所有符合条件的序列。以下是四种实现该目标的算法详解。

方法一：固定层级穷举法

第1步：理解局限性

对于小规模且 r 固定的情况，可以使用多重嵌套 for 循环直接遍历所有可能的组合。这种方法逻辑简单，但缺乏通用性：r 每增加 1，就需要额外增加一层循环，无法编写一个统一函数处理任意 r 值。

#include <stdio.h>
const int n=5, r=3;
int i, j, k, counts=0;

int main() {
    // 注意：实际应用中需根据r动态调整循环层数或改用其他算法
    for(i=1; i<=r-2; i++)
        for(j=i+1; j<=r-1; j++)
            for(k=j+1; k<=r; k++){
                counts++;
                printf("%4d %4d %4d\n", i, j, k);
            }
    printf("Total: %d\n", counts);
    return 0;
}

方法二：通用递归法

第1步：设计递归逻辑

递归法的核心思想是将“从 m 个数中选 k 个”转化为“从 m-1 个数中选 k-1 个”。设工作数组 a[] 存放当前确定的数字，约定将选定的第 k 个数字放入 a[k]。从最大值 m 开始向前枚举，若已选出全部 k 个数则输出，否则继续递归。

第2步：代码实现与测试

以下代码实现了通用递归求解，并通过计时器评估耗时。该方法简洁且具有通用性，适合中等规模的数据处理。

#include <iostream>
#include <time.h>
using namespace std;

#define MAXN 100
int a[MAXN];
int counts = 0;

void printtime() {
    char tmpbuf[128];
    time_t ltime;
    struct tm *today;
    time(&ltime);
    today = localtime(&ltime);
    strftime(tmpbuf, 128, "%Y-%m-%d %H:%M:%S", today);
    cout << tmpbuf << endl;
}

void comb(int m, int k) {
    int i;
    // 从m向下枚举到k
    for (i=m; i>=k; i--) {
        a[k] = i;
        if (k > 1)
            comb(i - 1, k - 1); // 递归处理剩余k-1个数
        else {
            counts++; // 找到一个完整组合
            // 可在此处添加打印逻辑：for(int j=1;j<=r;j++) ... 
        }
    }
}

int main() {
    int m, r;
    cout << "Enter m: "; cin >> m;
    cout << "Enter r: "; cin >> r;
    
    counts = 0;
    a[0] = r; // 标记数组有效长度
    
    printtime();
    comb(m, r);
    cout << "Total counts: " << counts << endl;
    printtime();
    
    return 0;
}

方法三：智能回溯法（推荐）

第1步：分析回溯特性

回溯法通过维护一个定位数组 a[]（存储的是元素在原集合中的索引或具体值），按从小到大顺序存储组合。其满足两个关键性质： 1. a[i+1] > a[i]：严格递增。 2. a[i] - i <= n - r + 1：保证后续还有足够的数字可选。

第2步：初始化与迭代查找

程序初始化为最小合法组合 (0, 1, ..., r-1)。通过 do-while 循环不断寻找下一个更大的组合。如果当前位未达到上限则自增；若达到上限则回溯前一位并重置后续位，直至全部组合遍历完毕。

第3步：完整代码实现

此版本优化了输出接口，数组使用 0 起始索引，便于映射到任意类型的输入数组。在实际基准测试中（g++ -O2，n=40, r=11），其执行时间约为 19-20 秒，略优于纯递归法的 23-24 秒。

#include <iostream>
#include <time.h>
#include <iomanip>
using namespace std;

#define MAXN 100
int a[MAXN]; // 存储组合元素的原始索引（0-based）

// 回溯法核心逻辑
void comb_backtrack(int m, int r) {
    int cur; // 当前正在调整的位置
    unsigned int count = 0;

    // 1. 初始化：a[0]=0, a[1]=1, ... a[r-1]=r-1
    for(int i=0; i<r; i++)
        a[i] = i;

    cur = r - 1;

    do {
        // 检查当前位置是否可以增加
        if (a[cur] - cur <= m - r) {
            count++;
            // 此处可添加打印代码：输出当前a[]的内容
            a[cur]++; // 当前位前进一格
            continue; 
        } else {
            // 到达边界，需要回溯
            if (cur == 0) {
                cout << "Total: " << count << endl;
                break; // 已完成所有组合
            }
            
            // 回溯到上一位并进位
            a[--cur]++;
            // 重置后面所有位为连续的最小值
            for(int i=1; i<r-cur; i++) {
                a[cur+i] = a[cur] + i;
            }
            
            // 重置指针到最后一位继续试探
            cur = r - 1;
        }
    } while (1);
}

void printtime() {
    // 同前，省略具体实现以保持简洁
    char tmpbuf[128];
    time_t ltime;
    struct tm *today;
    time(&ltime);
    today = localtime(&ltime);
    strftime(tmpbuf, 128, "%Y-%m-%d %H:%M:%S", today);
    cout << tmpbuf << endl;
}

int main() {
    int m, r;
    cout << "Enter m: "; cin >> m;
    cout << "Enter r: "; cin >> r;
    
    printtime();
    comb_backtrack(m, r);
    printtime();
    return 0;
}

方法四：基于二进制数组变换法

第1步：理解“10”交换原理

该方法不使用数值递归，而是创建一个长度为 n 的布尔型（或整型）数组。下标代表原数字，值为 1 表示被选中，0 表示未选中。初始状态为前 r 个元素为 1（即 1...10...0）。
生成下一个组合的逻辑是：从左向右扫描，找到第一个 “10” 模式，将其交换为 “01”。然后，将该 “10” 左侧所有的 1 都移到最左边，0 移到最后方。当所有的 1 都移动到数组最右端时，即完成所有组合。

第2步：演示过程

以 n=5, r=3 为例：

• 1 1 1 0 0 -> 对应 {1, 2, 3}
• 找到右侧第一个 '10' (位置2,3)，交换得 '01'，左边一个'1'提到最前 -> 1 1 0 1 0 -> 对应 {1, 2, 4}
• 重复上述过程，直到状态变为 0 0 1 1 1 -> 对应 {3, 4, 5}

总结与选型建议

综合比较这四种方法： 1. 穷举法：仅适用于 r 极小且固定的教学场景，工程价值低。 2. 递归法：代码最短，逻辑清晰，适合快速原型开发。 3. 回溯法：效率高，逻辑严密，且易于转换为非递归结构，是工业级首选方案之一。 4. 数组变换法：避免了函数调用开销，但在大规模 n 时内存管理较为繁琐，适合特定硬件或底层优化场景。

以上就是C++中求组合数的各种方法总结详解，更多关于C++算法优化的资料请关注本站其它相关文章！