递归获得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

有一个更容易（更快）的方式来计算组合 - 这是binomial coefficient。虽然我可以理解你的老师可能希望你通过这种方式编写递归函数来熟悉递归，但可以使用这个公式作为检查。

就你而言，你在这里报告错误的期望值。你想要的是

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

和你发布的代码是正确的，如果上面的值是它应该返回的。

（如果没有，也许你可以更好地解释更清楚问题如何你从binomial coefficient解决不同澄清这个问题。）