,給出總和 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}
等 可以有更多。 也可以找到這些子集的總數。 請幫我解決這個問題..查找給定元素數組(所有元素都是唯一的)中的元素總和爲
回答
下面是一些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)
將來自生成器的所有值放入一個列表中(這會消耗生成器,試着在之前/之後迭代它)。
既然你不說,如果是功課與否,我只給出一些提示:
讓
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 dnums[i]
在R_s'
每一集,並將它們添加到您的結果R_s
解決您的問題,通過實施
find
,並呼籲find(0, 10)
我希望這有助於
這是一個可以通過遞歸解決的着名的回溯問題。基本上它是一種蠻力方法,其中嘗試了每種可能的組合,但是給出了至少修剪搜索的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.
如果任何條件失敗,該分支被終止。
- 1. 查找數組,等於剩餘的元素的總和元素
- 2. 檢查元素是否爲給定元素的父元素
- 3. 查找二維數組中所有元素的總和
- 4. 查找出現在所有給定的數組中的元素
- 5. 如何查找數組中給定元素的所有索引?
- 6. 查找與給定總和相等的數組元素
- 7. MongoDB:按數組元素查找元素
- 8. 查找具有指定嵌套子元素的所有元素
- 9. 給數組元素的唯一ID
- 10. 數組的總和元素
- 11. 數組元素的總和
- 12. 查找與特定元素相交的所有元素 - RaphaelJs
- 13. 在python列表中查找元組中的唯一元素
- 14. 查找列表中的唯一元素
- 15. 如何查找數組中大於其後所有元素的元素數量?
- 16. 查找兩個元素之間的數組中的所有元素
- 17. 查找特定元素的數組與重複元素
- 18. 如何在一組DOM元素中找到具有給定ID的元素?
- 19. 如何查找元素中的元素
- 20. 確定是否所有元素的數組是素數
- 21. 在PHP中查找數組元素的所有可能的唯一組合
- 22. XmlReader認爲所有元素都是EndElements
- 23. 查找連續元素相差1的數組中的元素
- 24. 總和數組元素
- 25. 在Java中查找元素數組中的元素
- 26. 在另一個元素中查找所有錨元素的xpath是什麼?
- 27. 元素在給定範圍內的子矩陣中唯一元素的數量?
- 28. 查找元素的唯一子節點
- 29. 查找一組元素
- 30. 查找數組中圍繞元素的元素
由於這_seems_家庭作業,我建議張貼你試過的東西,所以我們可以幫助你通過那 – 2011-04-18 11:52:17
這是NP完整。然後做一個激烈的搜索。 – hugomg 2011-04-18 13:49:04
@missingno:搜索不一定是詳盡無遺的:你不需要使用輸入數組的值大於目標總和的元素 – MarcoS 2011-04-18 14:07:34