C++组合数学算法详解（从零开始掌握排列组合编程技巧）

1. 计算组合数 C(n, m)

组合数公式为：

C(n, m) = n! / (m! * (n - m)!)

但直接计算阶乘容易溢出，因此我们通常采用递推或动态规划的方式。

方法一：递归 + 记忆化（适合小数据）

#include <iostream>#include <vector>using namespace std;const int MAXN = 100;vector<vector<long long>> memo(MAXN, vector<long long>(MAXN, -1));long long comb(int n, int m) {    if (m == 0 || m == n) return 1;    if (memo[n][m] != -1) return memo[n][m];    return memo[n][m] = comb(n - 1, m - 1) + comb(n - 1, m);}int main() {    cout << "C(5, 2) = " << comb(5, 2) << endl; // 输出 10    return 0;}

方法二：动态规划（推荐）

利用帕斯卡三角形（Pascal's Triangle）构建组合数表：

#include <iostream>#include <vector>using namespace std;vector<vector<long long>> buildCombTable(int n) {    vector<vector<long long>> C(n + 1, vector<long long>(n + 1, 0));    for (int i = 0; i <= n; ++i) {        C[i][0] = 1;        for (int j = 1; j <= i; ++j) {            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];        }    }    return C;}int main() {    auto table = buildCombTable(10);    cout << "C(10, 3) = " << table[10][3] << endl; // 输出 120    return 0;}

2. 生成所有排列（全排列）

C++ 标准库提供了 next_permutation 函数，可以高效生成字典序下一个排列。

#include <iostream>#include <algorithm>#include <vector>using namespace std;int main() {    vector<int> v = {1, 2, 3};    do {        for (int x : v) cout << x << " ";        cout << endl;    } while (next_permutation(v.begin(), v.end()));    return 0;}

3. 生成所有组合

我们可以用递归回溯法生成从 n 个元素中选 k 个的所有组合：

#include <iostream>#include <vector>using namespace std;void combine(vector<int>& nums, int start, int k,               vector<int>& path, vector<vector<int>>& result) {    if (path.size() == k) {        result.push_back(path);        return;    }    for (int i = start; i < nums.size(); ++i) {        path.push_back(nums[i]);        combine(nums, i + 1, k, path, result);        path.pop_back(); // 回溯    }}int main() {    vector<int> nums = {1, 2, 3, 4};    vector<vector<int>> result;    vector<int> path;    combine(nums, 0, 2, path, result);    for (auto& combo : result) {        for (int x : combo) cout << x << " ";        cout << endl;    }    return 0;}

性能与适用场景

不同的 排列组合C++ 实现适用于不同场景：

• 小规模数据（n ≤ 30）：递归+记忆化足够快。
• 多次查询组合数：预处理动态规划表（O(n²) 预处理，O(1) 查询）。
• 生成所有组合/排列：使用回溯或 STL 函数，注意时间复杂度为指数级。

总结

掌握 组合数计算 和 递归与动态规划 在组合问题中的应用，是提升算法能力的关键一步。无论是面试还是竞赛，这些基础技巧都不可或缺。建议读者动手实现上述代码，并尝试修改参数观察输出结果，加深理解。

关键词回顾：C++组合数学算法、排列组合C++、组合数计算、递归与动态规划。