java - 一组整数按大小升序排列的 k 种组合

Question

编程挑战:给定一组整数 [1, 2, 3, 4, 5] 我想在 Java 中生成所有可能的 k 组合强>;例如

[1], [2], [3], [4], [5], [1, 2], [1, 3] ... [1, 2, 3, 4, 5]

生成一个生成所有组合然后对它们进行排序的递归解决方案相当容易，但我想有一种更有效的方法可以消除额外排序的需要。

Answer 1

就做iterative deepening search .

void comb(int... items) {
    Arrays.sort(items);
    for (int k = 1; k <= items.length; k++) {
        kcomb(items, 0, k, new int[k]);
    }
}
public void kcomb(int[] items, int n, int k, int[] arr) {
    if (k == 0) {
        System.out.println(Arrays.toString(arr));
    } else {
        for (int i = n; i <= items.length - k; i++) {
            arr[arr.length - k] = items[i];
            kcomb(items, i + 1, k - 1, arr);
        }
    }
}

然后调用 comb(10,20,30)。它将打印:

[10]
[20]
[30]
[10, 20]
[10, 30]
[20, 30]
[10, 20, 30]