std::next_permutation仅生成字典序全排列，不计算数量；需先排序且不适用于大n；算组合数应使用迭代公式防溢出，或Boost高精度库。
用 std::next_permutation 生成全排列，不是算组合数
很多人搜“C++ 排列组合数”，第一反应是调 std::next_permutation，但它只负责生成下一个字典序排列，不计算数量。它要求容器可排序（如 vector<int></int>），且初始必须升序（或调用前先 sort），否则会漏掉部分排列。
常见错误现象：next_permutation 返回 false 却没意识到是因为输入未排序；或者对含重复元素的数组直接用，导致结果重复或遗漏。
- 使用前务必
sort(v.begin(), v.end()) - 含重复值时，
next_permutation仍能去重——它按字典序跳过等价排列，但前提是元素本身可比较且已排序 - 性能上，生成全部排列是 O(n! × n)，仅适合 n ≤ 10；别用它来“算个数”，纯属浪费
用公式 + 长整型防溢出算 C(n,k) 和 P(n,k)
真要算组合数 C(n,k) 或排列数 P(n,k)，得手写公式：
C(n,k) = n! / (k! × (n−k)!)，
P(n,k) = n! / (n−k)!。
但直接算阶乘极易溢出，int 在 n > 12 就爆了，long long 也只撑到 n ≈ 20。
正确做法是边乘边除，把除法穿插进乘法过程，控制中间值不膨胀：
long long C(int n, int k) {
if (k n) return 0;
k = min(k, n - k); // 利用对称性降规模
long long res = 1;
for (int i = 1; i
- 关键点：
res * (n−k+i) / i的除法顺序不能颠倒，否则可能丢精度；整除安全的前提是每步都整除，数学上成立 -
P(n,k)更简单：直接连乘n × (n−1) × ... × (n−k+1)，同样建议用long long，且加溢出检查（比如乘前判断res > LLONG_MAX / (n−i)） - 若 n 较大（> 60）且只需模意义下结果，就得换快速幂 + 逆元或预处理阶乘逆元表
用 boost::math::binomial_coefficient 算高精度组合数
当 n 超过 64 位范围，又不想自己写大数，Boost.Math 提供了 binomial_coefficient，底层用 double 近似或 cpp_dec_float 高精度，取决于模板参数。
使用场景：科研计算、测试验证、n 在 1000 以内需精确值；不适用于嵌入式或无 Boost 环境。
- 头文件：
#include <boost></boost> - 精确整数计算：传
boost::multiprecision::cpp_int类型，如binomial_coefficient<cpp_int>(n, k)</cpp_int> - 注意：编译需链接 Boost，且
cpp_int运算比原生类型慢一个数量级以上，别在热循环里用
递归 + 记忆化求组合数容易栈溢出和重复计算
有人写 C(n,k) = C(n−1,k−1) + C(n−1,k) 递归，代码短但问题明显：不加记忆化就是指数级重复调用；加 map<pair>,ll></pair> 又引入哈希开销和内存碎片。
更糟的是，深递归（n > 500）直接触发栈溢出，而迭代版只要几行、零额外空间。
- 除非你在写教学示例或 n 极小（≤ 20），否则别用递归版
- 若坚持用动态规划，二维数组
dp[i][j]空间浪费严重，一维滚动数组足够：dp[j] = dp[j] + dp[j−1]，从后往前更新 - 所有 DP 写法都要注意边界：初始化
dp[0] = 1，且 j 不超过 min(i,k)
实际项目里，90% 的情况用迭代公式 + long long 就够了；真正卡精度或超大 n 的场景，往往已有专用数学库或需要定制大数逻辑。别为“看起来简洁”选递归，也别把生成器当计算器用。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
