经典Subset Sum问题递归DP代码调换递归顺序出错，原因是什么？

你当前的代码核心问题是记忆化缓存的状态设计错误：

• 子集和问题的记忆化递归需要两个状态参数：当前遍历到的元素下标i、剩余需要凑出的和x，完整的状态定义应该是dp[i][x]：表示从下标0到i的元素中选取，是否可以凑出和为x
• 你只使用了一维数组dp[x]做缓存，完全忽略了i这个维度，相当于把不同i下的同x结果混存，必然会出现缓存冲突的问题。

为什么原递归顺序看起来可以正常运行？ #

你原来的递归顺序是「优先尝试选当前元素」：recurse(选第i个元素) or recurse(不选第i个元素)
这种执行顺序下，第一次给dp[x]赋值时，刚好是当前最大i下的正确结果，在部分测试用例中不会触发缓存冲突，属于碰巧适配了测试用例，本质上代码还是错误的，只要构造合适的测试用例，原顺序也会返回错误结果。

调换顺序后报错的具体逻辑 #

当你把递归顺序换成「优先尝试不选当前元素」：recurse(不选第i个元素) or recurse(选第i个元素)，会提前触发缓存冲突，我们以你给出的输入nums = [1,2,3,4,5,6,7]举实际冲突场景：

1. 假设目标x为可凑出的数值10，递归首先进入i=6（对应元素7）、x=10的调用，优先走「不选i=6」的分支，进入i=5（对应元素6）、x=10的调用
2. 在i=5、x=10的调用中，继续优先走「不选i=5」的分支，进入i=4（对应元素5）、x=10的调用
3. 假设前5个元素（1、2、3、4、5）凑10的路径还没算出来，递归继续往下走不选的分支，最终发现i < 0时x还不为0，就会给dp[10]赋值为0返回上层
4. 上层现在要走「选i=5」的分支，也就是需要计算recurse(nums, 10-6=4, i=4)，但如果后续任意递归调用中再次遇到x=10，不管当前i是多少，都会直接读取dp[10]中存的错误值0直接返回，完全漏掉了「选i=5的6，再从前面元素凑4」的正确路径，最终就会返回错误的False。

修复方案 #

方案1：补全记忆化的状态维度 #

把一维dp数组改成二维，同时缓存i和x两个维度的结果，此时递归顺序随便调换都不会出错：

int dp[200][20001]; // 第一维大小根据nums的最大长度调整
int recurse(vector<int>& nums, int x, int i) {
    if (x == 0)
        return 1;
    if (i < 0 or x < 0)
        return 0;
    if (dp[i][x] != -1)
        return dp[i][x];
    return dp[i][x] = recurse(nums, x, i - 1) || recurse(nums, x - nums[i], i - 1);
}
bool canPartition(vector<int>& nums, int x) {
    memset(dp, -1, sizeof dp);
    return recurse(nums, x, nums.size() - 1);
}

方案2：改用迭代版0-1背包（空间优化版） #

如果不想用递归，可以用标准的一维滚动数组迭代实现，注意内层循环倒序遍历即可：

bool canPartition(vector<int>& nums, int x) {
    vector<bool> dp(x + 1, false);
    dp[0] = true;
    for (int num : nums) {
        for (int j = x; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    return dp[x];
}

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