java - 了解使用数组中所有可能组合的递归

Question

我试图借助几个例子来理解递归。我发现这个示例使用递归打印给定大小 n 数组中的 r 元素的所有可能组合。

Print all possible combinations of r elements in a given array of size n.

他们正在使用表达式背后的想法:

我在这里试图理解的是这个表达式的概念含义。我读过不同的文章，但找不到令人满意的解释。

使用此表达式的数学或实际示例将非常有帮助。

Answer 1

首先，数学中的组合有不同的表示法:

使用第一个，你的公式是

它的左侧表示:我们可以从n个元素集中选择r个元素的方式数量。

令S为一组n元素。令x为它的最后一个元素，因此集合S例如为

+-------------+---+
| a b c d e f | x |
+-------------+---+

设C是集合S中r元素的任意组合。

(特别是，按照刚刚介绍的示例，您可以想象 r = 3 和 n = 7 - 因为集合是 {a, b 、c、d、e、f、x}。)

只有两种可能:

1. C 包含 x(例如 C = {a, d, x})，或
2. C 不包含 x(例如 C = {a, d, e})。

如果 C 包含 x，则剩余的 (r - 1) 元素(即我们示例中的 2 ) 是从剩余的 (n - 1) 元素中选择的(即我们示例中的 {a, b, c, d, e, f}) - 所以有

如何选择这种组合的方法。

如果 C 不包含 x，则从剩余 ( n - 1) 个元素 - 所以有

如何选择这种组合的方法。