如何不使用阶乘计算组合函数（choose function）的结果？

架构老林

2026-8-18

解决Java中组合数计算的溢出问题

简化计算规模：组合数具有对称性 C(n, k) = C(n, n−k)，计算前先判断，若k > n/2，将k替换为n−k，减少乘法运算次数。

分步乘除（约分）避免溢出：无需直接计算大阶乘，通过逐步乘除并约分的方式计算，利用组合数的整数性质，每一步运算结果均为整数，有效控制数值大小。
示例代码（适用于n、k较小的场景，返回long类型）：

public static long computeCombination(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
    // 取较小的k减少计算量
    k = Math.min(k, n - k);
    long result = 1;
    for (int i = 1; i <= k; i++) {
        result = result * (n - k + i) / i;
    }
    return result;
}

若n、k数值较大，long类型仍会溢出，可使用Java的BigInteger类处理任意大整数：

import java.math.BigInteger;

public static BigInteger computeBigCombination(int n, int k) {
    if (k < 0 || k > n) return BigInteger.ZERO;
    if (k == 0 || k == n) return BigInteger.ONE;
    k = Math.min(k, n - k);
    BigInteger result = BigInteger.ONE;
    for (int i = 1; i <= k; i++) {
        result = result.multiply(BigInteger.valueOf(n - k + i))
                      .divide(BigInteger.valueOf(i));
    }
    return result;
}