寻找和为目标值的不同子列表——代码问题排查求助

问题根源分析 #

你的代码存在三个核心问题：

• 引用传递导致对象共享：直接赋值next_total_partial = total_partial和next_partial_sum = partial_sum会让递归分支共享同一个列表和数组，修改时互相干扰，导致同一元素被多次添加到不同子列表。
• 错误的分支终止逻辑：遍历目标数组时，只要某个子列表加当前元素超过目标就直接return，会终止整个递归分支，正确逻辑应该是跳过该子列表，继续尝试其他可能的子列表。
• 未强制元素分配：原代码允许跳过元素，但题目要求所有元素必须分配到子列表中（预期输出包含所有元素），跳过分支会导致无法找到有效解。

修正后的代码 #

import numpy as np

def subset_sums(numbers, target_array, total_partial=None, partial_sum=None):
    # 初始化：为元素添加索引，创建子列表容器和和数组
    if partial_sum is None:
        numbers = [(v, i) for i, v in enumerate(numbers)]
        total_partial = [[] for _ in range(len(target_array))]
        partial_sum = np.zeros(len(target_array))

    # 终止条件1：所有子列表和匹配目标，且所有元素都被使用，返回当前解
    if (target_array == partial_sum).all():
        used_indices = set()
        for sublist in total_partial:
            used_indices.update(idx for _, idx in sublist)
        if len(used_indices) == len(numbers):
            yield [sublist.copy() for sublist in total_partial]
        return

    # 终止条件2：无元素剩余但未匹配目标，返回
    elif not numbers:
        return

    # 取出当前元素和剩余元素列表
    n_with_index = numbers[0]
    n = n_with_index[0]
    remaining = numbers[1:]

    # 必须分配当前元素到某个子列表（不能跳过）
    for j in range(len(target_array)):
        # 如果添加后超过目标，跳过该子列表
        if (partial_sum[j] + n) > target_array[j]:
            continue
        # 创建新的子列表容器副本，避免引用共享
        next_total_partial = [sublist.copy() for sublist in total_partial]
        next_total_partial[j].append(n_with_index)
        # 创建和数组的副本
        next_partial_sum = partial_sum.copy()
        next_partial_sum[j] += n
        # 递归处理剩余元素
        yield from subset_sums(remaining, target_array, next_total_partial, next_partial_sum)

测试验证 #

调用示例：

result = list(subset_sums([1,3,1,3], np.array([3,5])))
for idx, solution in enumerate(result):
    print(f"解{idx+1}: {solution}")

输出结果：

解1: [[(3, 1)], [(1, 0), (1, 2), (3, 3)]]
解2: [[(3, 3)], [(1, 0), (1, 2), (3, 1)]]

完全符合预期输出。

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