我需要找到由数字数组中的数字组成的大小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));
}
}
}
最佳答案
一种更有效的方法(既节省时间又节省内存)是将结果存储为 int[][]
而不是Collection<List<Integer>>
(我假设是 monthsComb
字段的类型)。你可以这样做,因为你知道如果你有 k 个数字,结果将是 Binomial(n, k)
n 个数字的组合。
另一种方法(如 @Phia-CM 建议)是实现算法的非递归版本。
我知道它们都不容易实现,但这就是提高效率的方法。
关于java - 查找给定数组大小中给定数字的所有组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37437224/