查找給定元素數組（所有元素都是唯一的）中的元素總和爲

Question

，給出總和 s找到所有具有和s的子集。 ex ex {5,9,1,3,4,2,6,7,11,10} 總和爲10 可能的子集是{10}, {6,4}, {7,3}, {5,3,2}, {6,3,1}等 可以有更多。 也可以找到這些子集的總數。 請幫我解決這個問題..

Answer 1

下面是一些python代碼做你想做的。它廣泛使用itertools，所以要了解它，你可能想看看itertools docs。

>>> import itertools 
>>> vals = (5,9,1,3,4,2,6,7,11,10) 
>>> combos = itertools.chain(*((x for x in itertools.combinations(vals, i) if sum(x) == 10) for i in xrange(len(vals)+1))) 
>>> for c in combos: print c 
... 
(10,) 
(9, 1) 
(3, 7) 
(4, 6) 
(5, 1, 4) 
(5, 3, 2) 
(1, 3, 6) 
(1, 2, 7) 
(1, 3, 4, 2) 

它能做什麼基本上是這樣的：

• 對於所有可能的子集的大小 - for i in xrange(len(vals)+1)，做到：
• 遍歷所有子集與此尺寸 - for x in itertools.combinations(vals, i)
• 測試，如果總和子集的值爲10 - if sum(x) == 10
• 在這種情況下，產生子集

對於每個子集大小，都會生成另一個生成器，因此我使用itertools.chain將它們鏈接在一起，因此只有一個生成器生成所有解決方案。

由於您只有一個生成器而不是一個列表，因此您需要在迭代它時對這些元素進行計數 - 或者可以使用list(combos)將來自生成器的所有值放入一個列表中（這會消耗生成器，試着在之前/之後迭代它）。

Answer 2

既然你不說，如果是功課與否，我只給出一些提示：

• 讓nums是您可以使用（在你的例子nums = {5,9,1,3,4,2,6,7,11,10}）

• 號數組

  讓targetSum是你給出的（在你的榜樣targetSum = 10）和值

• 排序nums：你不希望搜索使用ELE解決方案這是更大的targetSum

• 放開的nums發言：S_s是一組來自nums其總和取整數等於s

• 讓R_s是集合所有S_s

• 你想

  找到R_s（在你的例子中爲R_10）

• 現在，假設喲u有一個功能find(i, s)使用nums的子陣列返回R_s如果nums[i] == s你從位置i

  • 如果nums[i] > s可以停止（請記住，你以前來分類nums）

  • 開始找到R_s = { { nums[i] } }，因此返回

  • 對於每個j in [1 .. nums.length - 1]要計算R_s' = find(i + j, targetSum - nums[i])，則ad d nums[i]在R_s'每一集，並將它們添加到您的結果R_s

• 解決您的問題，通過實施find，並呼籲find(0, 10)

我希望這有助於

Answer 3

這是一個可以通過遞歸解決的着名的回溯問題。基本上它是一種蠻力方法，其中嘗試了每種可能的組合，但是給出了至少修剪搜索的3個邊界條件。
以下是算法：
s變量，用於到目前爲止所選元素的總和。
r變量爲剩餘數組的總和。
M是所需的總和。
k是指數從0開始
w是

Sum(k,s,r) 
{ 
    x[k]:=1; //select the current element 
    if(s<=M & r>=M-s & w[k]<=M-s) 
    then 
    { 
     if(s+w[k]==M) 
     then output all i [1..k] that x[i]=1 
     else 
     sum(k+1,s+w[k],r-w[k]) 
    } 
    x[k]:=0 //don't select the current element 
    if(s<=M) & (r>=M-s) & (w[k]<=M-s) 
    then 
    { 
     if (M==s) 
     then output all i [1..k] that x[i]=1 
     else 
     sum(k+1,s,r-w[k]) 
    } 
} 

我使用的陣列的「x」標記選定爲溶液中的候選數字給定整數數組。在每個步驟3檢查邊界條件：

1. Sum of selected elements in "x" from "w" shouldn't exceed M. s<M.  
2. Remaining numbers in array should be able to complete M. r>=M-s. 
3. Single remaining value in w shouldn't overflow M. w[k]<=M-s. 

如果任何條件失敗，該分支被終止。