当前位置：首页 > Java

java如何求组合

2026-03-22 21:58:51Java

求组合的方法

在Java中，计算组合数（即从n个元素中选取k个的组合数）可以通过多种方法实现。以下是几种常见的实现方式：

递归法

递归法是最直观的方法，基于组合数的递推公式： [ C(n, k) = C(n-1, k-1) + C(n-1, k) ]

public static int combination(int n, int k) {
    if (k == 0 || k == n) {
        return 1;
    }
    return combination(n - 1, k - 1) + combination(n - 1, k);
}

缺点：递归法效率较低，尤其是对于较大的n和k，会出现重复计算的问题。

动态规划法

动态规划法通过填表的方式避免重复计算，提高效率。

public static int combination(int n, int k) {
    int[][] dp = new int[n + 1][k + 1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= Math.min(i, k); j++) {
            if (j == 0 || j == i) {
                dp[i][j] = 1;
            } else {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }
    }
    return dp[n][k];
}

优点：避免了递归的重复计算，时间复杂度为O(nk)，空间复杂度为O(nk)。

数学公式法

组合数的数学公式为： [ C(n, k) = \frac{n!}{k!(n-k)!} ]

为了避免直接计算阶乘导致的数值溢出，可以优化计算过程。

public static int combination(int n, int k) {
    if (k > n - k) {
        k = n - k; // 利用组合数的对称性减少计算量
    }
    int result = 1;
    for (int i = 1; i <= k; i++) {
        result = result * (n - k + i) / i;
    }
    return result;
}

优点：计算效率高，避免了阶乘的直接计算，减少了溢出的风险。

使用BigInteger

对于非常大的组合数，可以使用BigInteger来避免整数溢出的问题。

import java.math.BigInteger;

public static BigInteger combination(int n, int k) {
    if (k > n - k) {
        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;
}

优点：适用于非常大的n和k，不会出现溢出问题。

生成所有组合

如果需要生成所有可能的组合（而不仅仅是计算组合数），可以使用回溯法。

import java.util.ArrayList;
import java.util.List;

public static List<List<Integer>> generateCombinations(int n, int k) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), 1, n, k);
    return result;
}

private static void backtrack(List<List<Integer>> result, List<Integer> temp, int start, int n, int k) {
    if (temp.size() == k) {
        result.add(new ArrayList<>(temp));
        return;
    }
    for (int i = start; i <= n; i++) {
        temp.add(i);
        backtrack(result, temp, i + 1, n, k);
        temp.remove(temp.size() - 1);
    }
}

说明：该方法生成从1到n的所有k个元素的组合，结果以列表形式返回。

java如何求组合