特定子集總和的解決方案數量

假設我們有一個集合：{1,2，...，n}。存在多少個階數爲R的子集S = {a_i1，a_i2，... a_iR}，其總和達到一定數量S ?.什麼是這個問題的遞歸？特定子集總和的解決方案數量

2014-03-12 Dragos

你寫了一些不起作用的東西;如果是的話，什麼？你能向解決方案展示任何工作嗎？ –

我試圖找到一個直接的公式，從編寫一個數字S作爲n個整數的總和開始，然後我嘗試添加域限制，但是這並沒有帶我到任何地方。我的第二種方法是找到一個遞歸。很顯然，我可以將R數字的總和看作是將一個數字加到R-1數字的總和上。所以這是一個動態的問題。我要添加的最後一個數字是來自集{1,2，...，n}，所以我應該使用T_（R-1，S），T_（R-1，S-1），...，T_ （R - 1，S - n）。（T_（R，S）從1 ... n中加上R個數的方法總和爲S），但是我找不到係數 – Dragos

只是定義解決原始問題的方法。它接收參數是：使用

最大數量（n），
子集大小（R），
子集和（S），

並返回的組合數。

要實現這個方法，首先我們必須檢查是否可以提出這個請求。這是不可能完成的任務，如果：

子集大小比可能的元件（R> N）的數目
最大可能總和大於S. n + (n-1) + ... + (n-R+1) < S => R*((n-R) + (R+1)/2) < S較小

它之後較大足以嘗試所有可能的更大的元素，將進入子集。在Python風格，它應該像這樣實現：

def combinations(n, R, S): 
    if R > n or R*((n-R) + (R+1)/2) < S: 
    return 0 
    c = 0 
    for i in xrange(R, n+1): # try i as maximal element in subset. It can go from R to n 
    # recursion n is i-1, since i is already used 
    # recursion R is R-1, since we put i in a set 
    # recursion S is S-i, since i is added to a set and we are looking for sum without it 
    c += combinations(i-1, R-1, S-i) 
    return c

來源

2014-03-13 09:40:14 Ante

特定子集總和的解決方案數量

回答

相關問題