Python递归求目标和组合：如何用列表替代字符串存储组合

核心思路 #

原代码通过字符串拼接传递组合，因为字符串是不可变对象，每次拼接都会生成新字符串，不会影响上层递归逻辑。换成列表后，由于列表是可变对象，直接append会修改同一个列表，导致后续递归与上层递归共享列表元素，出现列表持续增大的问题。解决方法有两种：

• 每次递归时传递新的列表副本，和原代码的字符串拼接逻辑完全对齐；
• 使用回溯法：递归前添加元素，递归结束后移除元素，复用同一个列表以节省内存。

方法一：传递新列表副本（与原代码逻辑一致） #

把原代码中的字符串拼接替换为列表拼接（current_comb + [i]），每次递归生成新列表，避免修改上层递归的列表。同时用sum(current_comb)替代自定义的findSum函数。

修改后的完整代码：

import copy

def combination_sum(my_list, current_comb, X, N, count):
    # 达到最大递归深度，终止
    if count == int(N / X[0]) + 1:
        return

    # 当前组合和为N，存入结果列表
    if sum(current_comb) == N:
        my_list.append(copy.deepcopy(current_comb))
        return

    # 遍历集合元素，递归生成新组合
    for i in X:
        combination_sum(my_list, current_comb + [i], X, N, count + 1)

if __name__ == "__main__":
    N = 5
    X = [1, 2, 3]
    X.sort()
    current_comb = []
    my_list = []

    combination_sum(my_list, current_comb, X, N, count=0)
    print(my_list)

方法二：回溯法（更高效，避免重复创建列表） #

回溯法通过复用同一个列表，在递归前添加元素，递归完成后移除最后添加的元素，减少内存开销。还可以增加提前剪枝逻辑（比如当前和超过N时直接终止），优化递归效率：

import copy

def combination_sum(my_list, current_comb, X, N, count):
    max_depth = int(N / X[0]) + 1
    current_sum = sum(current_comb)
    # 提前剪枝：当前和超过N或达到最大深度，终止递归
    if current_sum > N or count == max_depth:
        return

    # 当前组合和为N，存入结果列表
    if current_sum == N:
        my_list.append(copy.deepcopy(current_comb))
        return

    # 遍历元素，执行回溯操作
    for i in X:
        current_comb.append(i)
        combination_sum(my_list, current_comb, X, N, count + 1)
        current_comb.pop()  # 回溯，移除最后添加的元素

if __name__ == "__main__":
    N = 5
    X = [1, 2, 3]
    X.sort()
    current_comb = []
    my_list = []

    combination_sum(my_list, current_comb, X, N, count=0)
    print(my_list)

关键说明 #

• 两种方法都实现了用列表存储组合，利用Python内置的sum()函数替代自定义求和逻辑；
• 方法一逻辑简单直观，与原代码结构高度匹配，但每次递归都会创建新列表，大N场景下存在性能损耗；
• 方法二的回溯逻辑更高效，复用列表减少内存占用，额外的剪枝操作还能进一步减少递归次数；
• 将组合存入结果列表时必须使用copy.deepcopy()，否则后续修改current_comb会影响已存入结果的列表内容。

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