一千萬個為什麽

搜索

按升序大小順序的一組整數的k組合

編程挑戰:給定一組整數[1,2,3,4,5]我想在 Java 中以升序大小順序生成所有可能的k組合;例如

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

生成一個生成所有組合然後對它們進行排序的遞歸解決方案相當容易,但我想有一種更有效的方法可以消除對額外排序的需求。

最佳答案

只需叠代深化搜索即可。

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]

轉載註明原文: 按升序大小順序的一組整數的k組合