java - 查找给定数组大小中给定数字的所有组合

Question

我需要找到由数字数组中的数字组成的大小n的所有组合。我尝试使用下面编写的函数来完成此操作，但这样做需要花费大量时间和内存。

有没有更高效的方法？

void createCombinationArray(ArrayList<Integer> numbers, int n, ArrayList<Integer> start) {
    if (start.size() >= n) {
        monthsComb.add(new ArrayList<>(start));
    } else {
        for (Integer x : numbers) {
            start.add(x);
            createCombinationArray(numbers, n, start);
            start.remove(start.lastIndexOf(x));
        }
    }
}

Answer 1

一种更有效的方法(既节省时间又节省内存)是将结果存储为 int[][]而不是Collection<List<Integer>> (我假设是 monthsComb 字段的类型)。你可以这样做，因为你知道如果你有 k 个数字，结果将是 Binomial(n, k) n 个数字的组合。

另一种方法(如 @Phia-CM 建议)是实现算法的非递归版本。

我知道它们都不容易实现，但这就是提高效率的方法。