Java如何实现任意k元素数组生成递增至指定最大值的所有组合序列

问题本质 #

你要实现的是从0~maxVal中选取k个元素的所有严格递增组合，对应数学上的组合枚举场景，你的思路本质是标准的「下一个组合」生成逻辑，只需要把递归实现改成迭代就能大幅提升效率，同时适配任意k值。

优化实现思路 #

每次生成下一个组合的迭代逻辑如下：

1. 从数组最后一位向前找，找到第一个满足arr[i] < maxVal - k + 1 + i的位置（这个值是当前位置i能取到的最大值）
2. 把这个位置的数值加1
3. 把这个位置之后的所有数值设为前一位的数值+1，保持严格递增
4. 如果找不到符合条件的位置，说明已经生成完所有组合

代码实现 #

迭代版nextCombi方法 #

// 返回null代表已经没有下一个组合
public static int[] nextCombi(int[] arr, int maxVal) {
    int k = arr.length;
    // 从后往前找可以自增的位置
    int i = k - 1;
    while (i >= 0 && arr[i] == maxVal - k + 1 + i) {
        i--;
    }
    // 所有位置都到最大值，没有下一个组合
    if (i < 0) {
        return null;
    }
    // 当前位置自增
    arr[i]++;
    // 后面的位置依次设为前一位+1
    for (int j = i + 1; j < k; j++) {
        arr[j] = arr[j - 1] + 1;
    }
    return arr;
}

主方法调用逻辑 #

public static void main(String[] args) {
    int k = 3; // 数组长度
    int maxVal = 4; // 最大值
    // 初始化数组
    int[] arr = new int[k];
    for (int i = 0; i < k; i++) {
        arr[i] = i;
    }
    // 遍历所有组合
    do {
        // 输出当前组合，可自行修改输出逻辑
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
        arr = nextCombi(arr, maxVal);
    } while (arr != null);
}

适配说明 #

这个实现自动适配任意k值，不需要修改核心逻辑，只要调整初始化时的数组长度即可。相比你原来的递归实现，没有函数调用的栈开销，也不会出现k较大时的栈溢出问题，性能提升非常明显。

内容的提问来源于stack exchange，提问作者KerubinGema Yuen