子集和（Subset Sum）问题代码错误排查求助（Interview Bit）

我在解决Interview Bit平台上的子集和（Subset Sum）问题时，采用选择/不选择数组元素、用left变量跟踪剩余目标和的思路，但自己编写的递归DP代码无法得到正确结果。

我的错误代码 #

class Solution:
    def solve(self, A, B):
        dp = []
        for _ in range(len(A)+1):
            dp.append([-1]*(B+1))
            
        def rec(index,left):
            if left < 0 or index==len(A):
                return False
            elif left == 0:
                return True
                
            if dp[index][left] != -1:
                return dp[index][left]
            
            dp[index][left] = rec(index+1,left) or rec(index+1,left-A[index])
            return dp[index][left]
            
        if rec(0,B):
            return 1
        else:
            return 0

正确的参考代码 #

class Solution:
    def solve(self, A, B):
        dp = [[-1 for _ in range(B+1)] for _ in range(len(A)+1)]
        
        def rec(index, left):
            if index == len(A):
                if left == 0:
                    return True
                else:
                    return False

            if dp[index][left] != -1:
                return dp[index][left]

            # 不选当前元素
            exclude = rec(index + 1, left)
            
            # 选当前元素
            include = False
            if left - A[index] >= 0:
                include = rec(index + 1, left - A[index])
            
            dp[index][left] = exclude or include
            return dp[index][left]

        return int(rec(0, B))

错误原因分析 #

1. 终止条件逻辑错误 #

你的代码在index == len(A)时直接返回False，但忽略了核心合法场景：当遍历完所有数组元素后，剩余目标和left恰好为0，说明已经找到一组元素的和等于目标值，此时应该返回True。

比如测试用例A=[1,2], B=3：当选择两个元素时，递归会走到index=2（等于数组长度），此时left=0，你的代码返回False，但正确逻辑应该返回True，这直接导致结果错误。

2. 未提前过滤无效递归（次要问题） #

你的代码在调用rec(index+1, left-A[index])前，没有判断left - A[index]是否非负，导致会触发left < 0的条件返回False。虽然这个逻辑本身结果没错，但会产生不必要的无效递归，而正确代码通过提前判断避免了这种情况，效率更高。

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