求助：用Python递归实现两数子集和判断函数

核心思路 #

递归逻辑分为两个关键部分：

1. 终止条件：当数组长度小于2时直接返回false——毕竟凑出两数之和至少需要两个元素。
2. 递归分支：
   • 取出数组第一个元素，和后面所有元素逐一配对，检查两者之和是否等于目标值x，有匹配就返回true。
   • 如果当前元素没找到配对，就递归调用函数，传入去掉第一个元素的子数组和目标值x，继续检查剩余元素的组合。

代码实现（Python） #

def subSetSum(array, x):
    # 数组元素不足2个，无法形成两数之和
    if len(array) < 2:
        return False
    
    # 取第一个元素，与后续所有元素配对检查
    first_num = array[0]
    for num in array[1:]:
        if first_num + num == x:
            return True
    
    # 递归处理剩余子数组
    return subSetSum(array[1:], x)

测试案例 #

• subSetSum([1, 2, 3], 5) → 返回True（2 + 3 = 5）
• subSetSum([1, 4, 6], 10) → 返回True（4 + 6 = 10）
• subSetSum([2, 5, 7], 11) → 返回False
• subSetSum([9], 18) → 返回False

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