子集和为零的数量计算结果解读疑问

这段动态规划代码的问题出在初始化逻辑错误，导致空子集被重复计数，下面具体分析：

问题复现 #

输入[2,2]时，代码返回2，但实际只有空集{}的和为0，正确结果应该是1；而输入[2,-2]时返回2（对应空集和{2,-2}），看起来正确只是巧合。

原代码 #

const arr = [2, 2];
const n = arr.length;
const maxSum = 3;

const dp = new Array(n + 1);
for (let i = 0; i <= n; i++) {
  dp[i] = new Array(2 * maxSum + 1).fill(0);
}

for (let i = 0; i <= n; i++) {
  dp[i][maxSum] = 1;
}

for (let i = 1; i <= 2 * maxSum; i++) {
  dp[0][i] = 0;
}

for (let i = 1; i <= n; i++) {
  for (let j = -maxSum; j <= maxSum; j++) {
    const val = arr[i - 1];
    if (j - val + maxSum >= 0 && j - val + maxSum <= 2 * maxSum) {
      dp[i][j + maxSum] += dp[i - 1][j - val + maxSum];
    }

    if (j + maxSum >= 0 && j + maxSum <= 2 * maxSum) {
      dp[i][j + maxSum] += dp[i - 1][j + maxSum];
    }
  }
}
console.log(dp[n][maxSum])

错误原因分析 #

1. 重复初始化空子集：
   代码中for (let i = 0; i <= n; i++) { dp[i][maxSum] = 1; }这行，给每个i对应的「前i个元素的空子集」都预先赋值为1。但动态规划的转移逻辑中，dp[i][j] += dp[i-1][j]已经包含了「不选当前元素，继承前i-1个元素的所有子集」的情况——这其中就包括前i-1个元素的空子集。

   对于[2,2]的情况：

   • 初始化时dp[2][3]（对应和为0）被设为1。
   • 转移阶段，处理第二个元素时，dp[2][3] += dp[1][3]（dp[1][3]是前1个元素的空子集计数，值为1），最终dp[2][3] = 1 + 1 = 2，相当于把空子集算了两次。

2. 空子集初始计数被覆盖：
   随后的for (let i = 1; i <= 2 * maxSum; i++) { dp[0][i] = 0; }把dp[0][3]（对应空子集的和为0）重置为0，彻底打乱了初始状态的正确性，只是在[2,-2]的场景下刚好通过转移逻辑凑出了正确结果。

修正方案 #

只保留空子集的初始状态，删除错误的初始化循环：

const arr = [2, 2];
const n = arr.length;
const maxSum = 3;

const dp = new Array(n + 1);
for (let i = 0; i <= n; i++) {
  dp[i] = new Array(2 * maxSum + 1).fill(0);
}

// 仅初始化空子集：前0个元素，和为0的情况数是1
dp[0][maxSum] = 1;

for (let i = 1; i <= n; i++) {
  for (let j = -maxSum; j <= maxSum; j++) {
    const val = arr[i - 1];
    if (j - val + maxSum >= 0 && j - val + maxSum <= 2 * maxSum) {
      dp[i][j + maxSum] += dp[i - 1][j - val + maxSum];
    }

    if (j + maxSum >= 0 && j + maxSum <= 2 * maxSum) {
      dp[i][j + maxSum] += dp[i - 1][j + maxSum];
    }
  }
}
console.log(dp[n][maxSum]) // 输入[2,2]时返回1，输入[2,-2]时返回2，符合预期

总结 #

原代码的初始化逻辑错误导致空子集被重复计数，修正后仅保留空子集的初始状态，就能得到正确的子集和为0的数量。

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