遞歸獲得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解決不同澄清這個問題。）