这是生成所有k子集或k组合的经过充分研究的问题，无需递归即可轻松完成。
这个想法是要使大小数组
k保持输入数组中元素 索引 的顺序（顺序是从
0到的数字
n -1），顺序是递增的。（然后可以通过从初始数组中按这些索引获取项来创建 子集。）因此，我们需要生成所有此类索引序列。
第一个索引序列将是
[0, 1, 2, ... , k - 1]，在第二步将切换到
[0, 1, 2,..., k]，然后切换到
[0, 1, 2,... k + 1]等等。最后一个可能的顺序是
[n - k, n - k + 1, ..., n - 1]。
在每个步骤中，算法都会寻找最接近可以增加的最终物料，将其递增并填充到该物料的右侧。
为了说明，请考虑
n = 7和
k = 3。第一个索引序列是
[0, 1, 2]，然后
[0, 1,3]依此类推…在某些时候，我们有
[0,5, 6]：
[0, 5, 6] <-- scan from the end: "6" cannot be incremented, "5" also, but "0" can be[1, ?, ?] <-- "0" -> "1"[1, 2, 3] <-- fill up remaining elementsnext iteration:[1, 2, 3] <-- "3" can be incremented[1, 2, 4] <-- "3" -> "4"
因此，
[0, 5, 6]接着是
[1, 2, 3]，然后继续，依此类推
[1, 2, 4]。
码：
int[] input = {10, 20, 30, 40, 50}; // input arrayint k = 3; // sequence lengthList<int[]> subsets = new ArrayList<>();int[] s = new int[k]; // here we'll keep indices // pointing to elements in input arrayif (k <= input.length) { // first index sequence: 0, 1, 2, ... for (int i = 0; (s[i] = i) < k - 1; i++); subsets.add(getSubset(input, s)); for(;;) { int i; // find position of item that can be incremented for (i = k - 1; i >= 0 && s[i] == input.length - k + i; i--); if (i < 0) { break; } s[i]++; // increment this item for (++i; i < k; i++) { // fill up remaining items s[i] = s[i - 1] + 1; } subsets.add(getSubset(input, s)); }}// generate actual subset by index sequenceint[] getSubset(int[] input, int[] subset) { int[] result = new int[subset.length]; for (int i = 0; i < subset.length; i++) result[i] = input[subset[i]]; return result;}
