正在寻找修复算法的方法。用动态规划实现组合求和Ⅱ

Question

基本上，我正在尝试使用动态编程在python中实现combination sum II，我的目标是创建一个时间复杂度不为O（2^n）的程序，但我遇到了很多问题，在任何地方都找不到解决方案。下面是我迄今为止得到的代码，但它似乎没有给出任何输出。

预期输出：[1,2,3]，[1,5]，[2,4]

实际产出：字面上没有

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([])

创建子集后。

然而，这段代码有几个问题，从变量名到重复工作。看看其他几种解决子集求和问题的方法，或者只搜索“子集求和”，看看您的问题的许多现有解决方案。