寻找修复算法的方法.用动态规划实现组合和II

Question

基本上，我试图使用动态编程在python中实现组合和II，我的目标是创建一个没有时间复杂度为O(2^n)的程序，但我一直有很多问题，无法在任何地方找到解决方案。下面是我到目前为止得到的代码，但它似乎没有给出任何输出。

期望输出:[1,2,3]，[1,5]，[2,4]

实际输出:literal nothing

arr = [1,2,3,4,5]
def combinationSum(candidates, target):
counts = [0] * (target + 1)
for elem in candidates:
if elem <= target:
counts[elem] += 1

numbers = []
a = 1
while a <= target:
if counts[a] != 0:
numbers.append(a)
a += 1
subsets = [[]] * (target+1)
smallTarget = numbers[0]
while smallTarget <= target:
subset = []
for i in numbers:
if i > smallTarget:
break
if (((i == smallTarget) or (i <= smallTarget/2)) != True) :
continue
mList = subsets[smallTarget - i]
for j in mList:
if len(j) == 0 or j[0] >= i:
count = counts[number]
for k in j:
if k == i :
count -= 1
if count != 0:
tList = []
tList.append(i)
for l in j:
tList.append(l)

subset.add(tList)
subsets[smallTarget] = subset
smallTarget+=1
return subsets[target]

for i in combinationSum(arr, 6):
print(i)

Answer 1

要修复您的代码不打印答案，请在循环之前添加一个空子集求和为0:

subsets[0].append([])

然而，这段代码有几个问题，从变量名到重复工作。看看其他几种解决子集和问题的方法或者谷歌一下"子集和"查看您的问题的许多现有解决方案。