使用数组中所有可能的组合理解递归

Question

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

打印给定大小为 n 的数组中 r 个元素的所有可能组合。

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

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

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

Answer 1

首先，数学中的组合有不同的表示法：使用第一个，你的公式是它的左侧表示：我们可以从元素集中选择元素的方式的数量。rn让S是一组n元素。让它x成为它的最后一个元素，所以集合S是例如+-------------+---+| a b c d e f | x |+-------------+---+Let是集合中元素C的任意组合。 rS（特别是，按照刚刚介绍的示例，您可以想象r = 3, 和 n = 7- 因为集合是{a, b, c, d, e, f, x}。）只有两种可能：C包含x（例如C = {a, d, x}），或C不包含x （例如C = {a, d, e}）。如果Ccontains x，则从剩余元素(r - 1)（即2在我们的示例中）中选择剩余(n - 1)元素（即{a, b, c, d, e, f}在我们的示例中） - 所以有如何选择这样的组合。如果C不包含x，则从剩余元素中选择所有 元素 - 所以有r(n - 1)如何选择这样的组合。