递归得到n个人k组不同组合的个数

Question

我正在使用 Java 练习递归，但遇到了问题。我正在尝试创建一种称为“组”的方法，该方法需要一定数量的人和有多少个组，然后返回人和组的不同组合的数量。此外，组中人员的顺序并不重要，组的顺序也不重要。

到目前为止我的代码是：

public long groups(int n, int k) {
    if(k==1) return 1;
    if(k==n) return 1;
    else return groups(n-1, k) + groups(n-1, k-1);
}

但是它返回错误的值。前两行是基本情况，如果有 1 组，那么只有一种方法可以将人员分开，这是有道理的。另一种情况是，人数与组数一样多，在这种情况下，只有一种方法可以将他们分开，即每组一个人。最后一个语句是我认为我遇到问题的地方，我认为每次进行递归调用时，都必须取出一个人（n是人数，所以n-1）并且该人可以以太加入一个组 (k) 或创建自己的组 (k-1)。

我只是在弄清楚递归如何工作方面遇到了一些麻烦，并且需要一些帮助。

这些是我期望的值：

groups(2,1) = 1
groups(2,2) = 1
groups(3,2) = 3
groups(4,2) = 7
groups(4,3) = 6
groups(5,3) = 25

Answer 1

该部分的实现中缺少一些内容

...并且该人可以加入群组 (k) ...

我认为这个人可以加入“k”个组，所以代码必须是

    public long groups(int n, int k) {
        if(k==1) return 1;
        if(k==n) return 1;
        else return k * groups(n-1, k) + groups(n-1, k-1);
    }

（缺少乘以k）

Answer 2

有一种更简单（更快）的方法来计算组合 - 这就是二项式系数。虽然我可以理解您的老师可能希望您以这种方式编写递归函数以熟悉递归，但您可以使用此公式作为检查。

就您而言，您在此处报告了错误的预期值。您想要的是，

groups(2,1) = 2
groups(2,2) = 1
groups(3,2) = 3
groups(4,2) = 6
groups(4,3) = 4
groups(5,3) = 10

如果上面的值是它应该返回的值，那么您发布的代码就是正确的。

（如果没有，也许您可​​以通过更清楚地解释您正在解决的问题与 有何不同来更好地澄清问题二项式系数。）