两数之和(Two Sum)递归实现异常，无法返回符合要求的下标对

预期代码输出数字4和2对应的下标[0, 2]，因为4 + 2 = 6正好等于目标值target，但实际运行后初始代码返回的下标是[0, 1]。

初始版本代码及问题 #

初始实现代码如下：

nums = [4, 3, 2]
target = 6
        
total=0     
s=[]
k=[]
def two(i, total):
    if i== 2 or total == target:
        k.append(s.copy())
        return
        
    if i>=2 and total != target:
        return False
    
    s.append(i)
    two(i+1, nums[i]+nums[i+1])

two(0,  0)
print(k)

初始代码问题点：

• 终止条件逻辑错误：只要遍历到下标2，无论当前累加和是否等于目标值都会把当前下标组合存入结果，这是返回错误组合[0,1]的直接原因
• 配对逻辑有遗漏：递归仅计算相邻下标的元素和，没有覆盖0和2这类不相邻下标的配对场景
• 递归分支不完整：仅实现了选中当前下标继续遍历的逻辑，没有跳过当前下标遍历后续元素的分支，无法覆盖所有可能的两数组合

调整后版本代码 #

调整后的代码可正常处理长度为3的输入：

s=[]
def two_sum(target, nums, i, j):
    if j==len(nums):
        return []
    if nums[i]+nums[j] == target:
        s.append(i)
        s.append(j)
        return s
    
    if j>len(nums):
        return False
        
    for i in range(len(nums)):
        return two_sum(target, nums, i, j+1) or two_sum(target, nums, i+j, j+1)

优化提示 #

调整后的版本仍存在全局变量污染、下标越界风险、长数组适配性差的问题，可进一步补全递归遍历分支，移除全局变量存储结果的逻辑，或者直接使用哈希表的迭代实现，时间复杂度可优化到O(n)。

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