子集和问题0/1背包递归解法中memoization记忆化的作用疑问

核心认知错误 #

你混淆了「状态参数单调变化」和「状态不会重复」两个概念：

• 递归过程中i确实每次+1单调递增，sum也因为数组元素全为正，仅会保持不变或递增，这两点判断都没错
• 但不同的前序选择路径完全可以在同一个i下标位置得到相同的sum值，这就是重复状态的核心来源。

重复状态实际示例 #

举个简单可验证的例子，输入数组为[1, 1, 2]：

1. 路径1：选择下标0的1，不选择下标1的1，走到i=2时sum=1
2. 路径2：不选择下标0的1，选择下标1的1，走到i=2时sum=1

此时两条完全不同的递归路径命中了完全相同的(i=2, sum=1)状态，该状态后续的递归计算逻辑完全一致。如果没有记忆化缓存，程序会重复计算两次该状态下的所有子分支，当数组长度达到100时，这种重复计算会让时间复杂度上升到O(2^N)，根本无法在限制时间内跑完大测试用例，会出现超时、递归栈溢出等问题，最终被评测系统判定为Wrong Answer，并不是你的递归逻辑本身出错。

记忆化逻辑的作用 #

你的记忆化实现会将每个(i, sum)状态的计算结果缓存，每个状态仅会被计算一次：
本题中N<=100，所有元素总和最大为100*100=10^4，总状态数不超过100 * 10^4 = 1e6，完全可以在短时间内跑完，因此加了记忆化的代码可以正常通过评测。

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