C++递归函数变量无法更新问题（Partition Equal Subset Sum求解）

你的递归代码核心问题是没有利用子递归的返回结果，只是调用了递归函数但没处理返回值，导致子分支找到符合条件的划分时，结果无法向上传递，最终当前层的hasil始终是初始的false。

具体问题点 #

原代码中，当index != nums.size()时，你调用了两次递归，但完全忽略了它们的返回值。即使某个子递归分支返回true，当前层的hasil还是保持初始的false，只有当当前层刚好遍历完所有元素且sum1 == sum2时才会修改hasil，但这种情况只有当所有元素都不选（sum1和sum2都是0）或者全选到其中一个集合（另一个为0）才会触发，显然不符合题目要求。

修正后的代码 #

#include <bits/stdc++.h>
using namespace std;

bool solve(vector<int>& nums, int sum1, int sum2, int index){
    // 终止条件：遍历完所有元素，判断两个和是否相等
    if(index == nums.size()){
        return sum1 == sum2;
    }

    // 尝试将当前元素加入sum1，只要该分支返回true，直接返回true
    if(solve(nums, sum1 + nums[index], sum2, index + 1)){
        return true;
    }
    // 尝试将当前元素加入sum2，同理只要分支返回true就返回
    if(solve(nums, sum1, sum2 + nums[index], index + 1)){
        return true;
    }

    // 两个分支都没找到符合条件的划分，返回false
    return false;
}

int main()
{
    vector<int> nums{1,5,11,5};
    cout << boolalpha << solve(nums, 0, 0, 0) << endl;
    return 0;
}

关键修改说明 #

1. 简化终止逻辑：直接在index == nums.size()时返回sum1 == sum2，无需额外的分支判断，更简洁。
2. 利用递归返回值：每次递归调用后，判断返回结果，如果为true，立刻向上返回true，这样只要存在任意一个符合条件的划分，结果就能快速传递到顶层。
3. 提前终止不必要的递归：一旦某个分支找到解，就不再执行后续的递归，减少无效计算。

进一步优化（可选） #

为了避免重复计算，可以加入记忆化搜索，或者先判断数组总和是否为偶数（如果总和是奇数，直接返回false，因为无法分成两个和相等的子集），这能大幅提升效率：

#include <bits/stdc++.h>
using namespace std;

bool canPartition(vector<int>& nums) {
    int total = accumulate(nums.begin(), nums.end(), 0);
    // 总和为奇数，直接返回false
    if(total % 2 != 0) return false;
    int target = total / 2;
    // 转化为子集和问题：是否存在子集和为target
    function<bool(int, int)> dfs = [&](int index, int currentSum) {
        if(currentSum == target) return true;
        if(index >= nums.size() || currentSum > target) return false;
        // 选当前元素
        if(dfs(index + 1, currentSum + nums[index])) return true;
        // 不选当前元素
        if(dfs(index + 1, currentSum)) return true;
        return false;
    };
    return dfs(0, 0);
}

int main()
{
    vector<int> nums{1,5,11,5};
    cout << boolalpha << canPartition(nums) << endl;
    return 0;
}

这个优化版本将问题转化为子集和问题，只需要判断是否存在子集和等于总和的一半，减少了一个参数，逻辑更清晰，同时提前排除了总和为奇数的无效情况。

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