如何修复动态规划实现的Python版Combination Sum II无输出问题

核心错误点 #

• 变量名错误：代码中count = counts[number]行的number变量未定义，实际应该使用当前遍历的候选值i
• 方法调用错误：你声明的subset是列表类型，Python列表没有add()方法，需要改为append()添加元素
• 初始化错误：subsets = [[]] * (target+1)的写法会让所有下标对应的列表共享同一块内存地址，修改任意一个位置都会同步修改所有位置；同时你缺失动态规划的基础边界：凑出目标值0的唯一组合是空集，需要主动设置subsets[0] = [[]]，否则后续的子集遍历都会因为子问题结果为空直接跳过，导致最终无输出
• 边界判断瑕疵：部分冗余判断会过滤合法组合，可简化优化

修复后的代码 #

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 = [[] for _ in range(target+1)]
    subsets[0] = [[]]
    
    smallTarget = numbers[0]
    while smallTarget <= target:
        subset = []
        for i in numbers:
            if i > smallTarget:
                break
            # 过滤重复组合，保证非降序
            if not (i == smallTarget or i <= smallTarget/2):
                continue
            mList = subsets[smallTarget - i]
            for j in mList:
                if len(j) == 0 or j[0] >= i:
                    # 修正变量名错误
                    count = counts[i]
                    for k in j:
                        if k == i:
                            count -= 1
                    if count > 0:
                        tList = [i] + j
                        # 修正列表添加方法错误
                        subset.append(tList)
        subsets[smallTarget] = subset
        smallTarget += 1
    return subsets[target]

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

运行输出 #

[1, 2, 3]
[1, 5]
[2, 4]

和预期结果完全一致。

内容的提问来源于stack exchange，提问作者Parth Agarwal