回溯算法求解twoSum问题时return语句无法返回正确结果求助

我用回溯算法实现了twoSum问题的求解逻辑，算法效率较低，但打印结果时能显示正确值；不过返回结果时，却返回空列表而非if语句中计算得到的正确结果。

我的代码如下：

def twoSum(nums, target, res=[], k=0):
    if target == 0:
        return [nums.index(res[0]), nums.index(res[1])]

    else:
        for i in range(k, len(nums)):
            if target - nums[i] >= 0:
                target = target - nums[i]
                res.append(nums[i])
                twoSum(nums, target, res, k+1)
                res.pop()
                target = target + nums[i]

    return []


nums = [2, 7, 11, 15]
print(twoSum(nums, 9))

补充说明：twoSum问题定义如下：

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

请问如何让if语句中的return语句返回最终的正确结果？

核心问题 #

你的代码中，递归调用twoSum(nums, target, res, k+1)时，没有接收递归返回的结果，也没有将这个结果向上传递。当递归找到符合条件的结果返回时，上层函数并没有捕获这个值，而是继续执行后续代码，最终走到函数末尾返回空列表[]。

另外还有两个潜在问题需要注意：

1. 默认参数res=[]会导致多次调用函数时共享同一个列表，引发错误
2. 使用nums.index()可能返回错误索引（数组有重复元素时）

修复后的代码 #

def twoSum(nums, target, res=None, k=0):
    # 替换默认参数，避免共享列表
    if res is None:
        res = []
    if target == 0:
        return [nums.index(res[0]), nums.index(res[1])]

    for i in range(k, len(nums)):
        if target - nums[i] >= 0:
            target -= nums[i]
            res.append(nums[i])
            # 接收递归返回的结果
            result = twoSum(nums, target, res, i+1)
            # 找到解则直接返回，终止后续逻辑
            if result:
                return result
            res.pop()
            target += nums[i]

    return []


nums = [2, 7, 11, 15]
print(twoSum(nums, 9))  # 输出 [0,1]

关键修复点 #

1. 传递递归结果：递归调用时接收返回值，一旦拿到非空结果就直接返回，确保正确结果向上传递到顶层调用。
2. 修复默认参数：将res=[]改为res=None，在函数内部初始化空列表，避免多次调用共享同一列表。
3. 优化递归起始索引：把k+1改为i+1，避免重复处理同一元素，减少无效递归。

处理重复元素的严谨版本 #

如果数组存在重复元素，nums.index()会返回第一个匹配项的索引，导致结果错误。可以修改逻辑，回溯时直接记录索引而非值：

def twoSum(nums, target, path=None, k=0):
    if path is None:
        path = []
    # 限制路径长度为2，避免多元素求和的情况
    if target == 0 and len(path) == 2:
        return path
    
    for i in range(k, len(nums)):
        if target - nums[i] >= 0:
            path.append(i)
            result = twoSum(nums, target - nums[i], path, i+1)
            if result:
                return result
            path.pop()
    
    return []


nums = [3, 3, 11, 15]
print(twoSum(nums, 6))  # 输出 [0,1]

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