递归实现子集和判断函数存在bug，部分输入结果异常求排查

问题场景 #

要实现一个递归函数，判断能否从给定数组中选取不重复元素组合出指定的targetSum。当前暴力递归逻辑为：

• 若当前元素加入currSum后等于targetSum，返回true
• 若加入后超过targetSum，返回false
• 否则先检查包含当前元素的情况，再检查不包含当前元素的情况

但部分输入结果不符合预期：

• 输入数组[4,18,5,9]、targetSum=14时，程序返回false，但实际5+9=14应返回true
• 输入数组[4,11,5,9]、targetSum=14时，程序返回true（结果正确）

当前代码如下：

递归函数代码

bool checkSum(vector<int> v, int idx, int currSum, int targetSum){
    if(idx == v.size()) return false;
    if(currSum+v[idx] == targetSum) return true;
    if(currSum+v[idx] > targetSum) return false;
    bool ans = checkSum(v, idx+1, currSum+v[idx], targetSum);
    if(ans) return true;
    ans = checkSum(v, idx+1, currSum, targetSum);
    return ans;
}

驱动代码

int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    for(auto &it:v){
        cin>>it;
    }
    int targetSum;
    cin>>targetSum;
    cout<<(checkSum(v,0,0,targetSum)?"true":"false");
}

错误原因 #

问题出在遇到大元素时直接终止了所有后续分支。当currSum + v[idx] > targetSum时，代码直接返回false，但此时应该跳过这个大元素，继续尝试后面的元素组合——毕竟当前元素太大不能选，但后面的元素仍有可能凑出目标和。

以出错的例子[4,18,5,9]、targetSum=14为例：

1. 初始currSum=0，idx=0，加4后为4小于14，进入包含4的分支
2. 到idx=1，4+18=22>14，代码直接返回false，完全没机会尝试跳过18的分支
3. 回到idx=0的不包含分支，currSum仍为0，idx=1时0+18>14，又直接返回false，根本没走到后面的5和9

修复方案 #

把if(currSum+v[idx] > targetSum) return false;改成直接进入不包含当前元素的递归分支，而非直接返回false。这样就算当前元素太大，仍能继续尝试后续元素的组合。

修复后的递归函数

bool checkSum(vector<int> v, int idx, int currSum, int targetSum){
    if(idx == v.size()) return false;
    int currentTotal = currSum + v[idx];
    if(currentTotal == targetSum) return true;
    
    // 当前元素过大，直接跳过，尝试后续元素
    if(currentTotal > targetSum){
        return checkSum(v, idx+1, currSum, targetSum);
    }
    
    // 先尝试包含当前元素的情况
    bool include = checkSum(v, idx+1, currentTotal, targetSum);
    if(include) return true;
    // 再尝试不包含当前元素的情况
    return checkSum(v, idx+1, currSum, targetSum);
}

额外优化建议 #

• 传递数组时使用const vector<int>& v，避免每次递归拷贝整个数组，提升性能
• 可先对数组排序，遇到第一个大于剩余目标值的元素时直接剪枝，进一步优化效率（上述修复已解决核心问题）

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