求具有n个元素的集合的k个元素子集的递归方法

Question

考虑寻找具有n个元素的集合的k个元素子集的问题。编写一个递归函数，该函数以表示集合的整数数组、集合中整数的数量(n(和所需的子集大小(k(作为输入，并在屏幕上显示所有具有k个元素的子集。您可以假设数组中的元素具有唯一的值。例如，如果数组(集合(包含元素[8 2 6 7]，n为4，k为2，则输出为82 86 87 26 27 67。

你能帮我做这件事吗？至少告诉我该怎么做？

Answer 1

你所说的东西类型是**组合&amp；。维基百科页面的中间隐藏着一个计算的递归定义。

$$\binom｛n｝｛k｝=\binom｝n-1｝{k-1｝+\binom

弄清楚你的基本情况可能很棘手，但我认为你需要的一切都在那里。

Answer 2

我会纠正这样的错误：

subset ( numbers, n, k, index)
{
if (index < n) // end for the recursion. passed through all elements
{
if (k == 0) // end for the recursion. no more elements needed
print ' '
else
{
print numbers[index]
subset(numbers, n, k-1, index+1) // uses the number in the current index
subset(numbers, n, k, index+1)   // doesn't use the number in the current index
}
}
call subset(numbers, n, k, 0) to start

注意，因为顺序在集合中不起作用，所以它足以在一个方向上传递元素