这是一个经过充分研究的生成所有 k 子集的问题,或者k-组合 https://en.wikipedia.org/wiki/Combination,无需递归即可轻松完成。
这个想法是有大小的数组k
保持顺序indices输入数组中的元素(这些数字来自0
to n - 1
)按递增顺序。 (Subset然后可以通过从初始数组中获取这些索引的项目来创建。)因此我们需要生成所有此类索引序列。
第一个索引序列将是[0, 1, 2, ... , k - 1]
,在第二步它切换到[0, 1, 2,..., k]
,然后到[0, 1, 2, ... k + 1]
等等。最后可能的序列将是[n - k, n - k + 1, ..., n - 1]
.
在每一步中,算法都会查找最接近可以递增的最终项目,递增它并填充该项目的右侧项目。
为了说明这一点,请考虑n = 7
and k = 3
。第一个索引序列是[0, 1, 2]
, then [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 elements
next iteration:
[1, 2, 3] <-- "3" can be incremented
[1, 2, 4] <-- "3" -> "4"
Thus, [0, 5, 6]
接下来是[1, 2, 3]
,然后去[1, 2, 4]
etc.
Code:
int[] input = {10, 20, 30, 40, 50}; // input array
int k = 3; // sequence length
List<int[]> subsets = new ArrayList<>();
int[] s = new int[k]; // here we'll keep indices
// pointing to elements in input array
if (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 sequence
int[] 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;
}