3 回答

TA貢獻(xiàn)1887條經(jīng)驗(yàn) 獲得超5個(gè)贊
這是帶有額外檢測(cè)的代碼,可幫助跟蹤輸出,縮進(jìn)遞歸調(diào)用。
您會(huì)注意到計(jì)數(shù)的一個(gè)嚴(yán)重問(wèn)題:當(dāng)您獲得所需的總數(shù)并到達(dá)列表末尾時(shí),您返回0而不是1。這會(huì)阻止您通過(guò)使用最終列表元素正確累積獲得正確總數(shù)的解決方案,因?yàn)樵跈z查是否獲得正確總數(shù)之前,您會(huì)重復(fù)超過(guò)列表末尾。維修在底部。
indent = ""
b = [2,3,2,1,4]
def subset_sum(total, idx):
global indent
print(indent + "ENTER", total, idx)
indent += " "
if total < 0 or idx < 0:
result = 0
elif total == 0:
result = 1
else:
result = subset_sum(total, idx-1) + subset_sum(total-b[idx], idx-1)
indent = indent[2:]
print(indent + "LEAVE", total, idx, result)
return result
if __name__ == "__main__":
print(subset_sum(5, 4))
輸出:
ENTER 5 4
ENTER 5 3
ENTER 5 2
ENTER 5 1
ENTER 5 0
ENTER 5 -1
LEAVE 5 -1 0
ENTER 3 -1
LEAVE 3 -1 0
LEAVE 5 0 0
ENTER 2 0
ENTER 2 -1
LEAVE 2 -1 0
ENTER 0 -1
LEAVE 0 -1 0
LEAVE 2 0 0
LEAVE 5 1 0
ENTER 3 1
ENTER 3 0
ENTER 3 -1
LEAVE 3 -1 0
ENTER 1 -1
LEAVE 1 -1 0
LEAVE 3 0 0
ENTER 0 0
LEAVE 0 0 1
LEAVE 3 1 1
LEAVE 5 2 1
ENTER 4 2
ENTER 4 1
ENTER 4 0
ENTER 4 -1
LEAVE 4 -1 0
ENTER 2 -1
LEAVE 2 -1 0
LEAVE 4 0 0
ENTER 1 0
ENTER 1 -1
LEAVE 1 -1 0
ENTER -1 -1
LEAVE -1 -1 0
LEAVE 1 0 0
LEAVE 4 1 0
ENTER 2 1
ENTER 2 0
ENTER 2 -1
LEAVE 2 -1 0
ENTER 0 -1
LEAVE 0 -1 0
LEAVE 2 0 0
ENTER -1 0
LEAVE -1 0 0
LEAVE 2 1 0
LEAVE 4 2 0
LEAVE 5 3 1
ENTER 1 3
ENTER 1 2
ENTER 1 1
ENTER 1 0
ENTER 1 -1
LEAVE 1 -1 0
ENTER -1 -1
LEAVE -1 -1 0
LEAVE 1 0 0
ENTER -2 0
LEAVE -2 0 0
LEAVE 1 1 0
ENTER -1 1
LEAVE -1 1 0
LEAVE 1 2 0
ENTER 0 2
LEAVE 0 2 1
LEAVE 1 3 1
LEAVE 5 4 2
2
修理
在檢查是否超出列表末尾之前,只需檢查是否成功:
if total == 0:
result = 1
elif total < 0 or idx < 0:
result = 0

TA貢獻(xiàn)1853條經(jīng)驗(yàn) 獲得超6個(gè)贊
您是否考慮過(guò)迭代方法?itertools.combinations想到
itertools.combinations(iterable, r)
從輸入可迭代返回 r 個(gè)長(zhǎng)度的元素子序列。
組合按字典排序順序發(fā)出。因此,如果輸入可迭代對(duì)象已排序,則組合元組將按排序順序生成。
有了這個(gè),您可以執(zhí)行以下操作:
from itertools import combinations
def count_subsets(main_list, target):
result = 0
for i in range(len(main_list)):
sets = combinations(main_list, i)
result += sum(sum(subset) == target for subset in sets)
return result

TA貢獻(xiàn)1831條經(jīng)驗(yàn) 獲得超10個(gè)贊
問(wèn)題是你在 idx < 0 時(shí)退出,但沒(méi)有先檢查是否 T == 0(這將是一個(gè)解決方案)。您應(yīng)該首先測(cè)試 T == 0:
if T == 0:
return 1
elif T < 0 or idx< 0:
return 0
else:
return subset_sum(T, idx-1) + subset_sum(T-b[idx], idx-1)
添加回答
舉報(bào)