力扣494这道“目标和”是我刷动态规划专题时卡得比较久的一道题。题面很短给你一个整数数组 nums 和一个目标值 target在每个数前面加或-构造一个表达式返回运算结果等于 target 的不同表达式数目。用 Java 实现时很多人第一反应就是 DFS 硬搜但真正把它吃透之后会发现这题是理解“0/1 背包求方案数”的最佳入口。这道题好在哪里它表面上是搜索题本质上是组合优化题。你既可以拿它练递归和回溯也可以拿它练记忆化搜索最后还能过渡到动态规划。一条题串起三种常用算法面试还经常追问变体属于那种“刷一遍顶三遍”的经典题。适合刚学完基础 DP、觉得背包问题抽象的同学也适合准备面试想系统整理“求方案数”类题型的读者。1. 题目拆解先看懂“目标和”到底在问什么1.1 原题描述与通俗解释题目原文大概是这样给你一个非负整数数组nums和一个整数target。向数组中的每个整数前添加或-然后串联起所有整数构造一个表达式返回可以通过上述方法构造的、运算结果等于target的不同表达式数目。举个例子nums [1, 1, 1, 1, 1]target 3答案是多少一共五个 1你要给每个 1 前面加正号或负号让整体结果等于 3。先别急着算最后我们会用这个例子验证所有解法是否正确。再比如nums [1]target 1答案就是 1表达式1正好等于 1。这个题用生活化的场景去理解就是一笔账比如你有五笔收入每笔金额是 1现在要给每笔钱标记“计入总收入”还是“计入总支出”最后希望“收入减去支出”正好等于 3。每个数字必须被使用而且必须二选一加上符号没有“不选”这个选项这就和普通的子集问题产生了微妙的区别。很多人做这道题觉得别扭就是因为在“选或不选”这件事上绕不过弯来。1.2 难点分析为什么不能靠暴力遍历最直觉的解法是枚举所有符号组合。数组长度是 n每个数有正负两种选择总共就是 2 的 n 次方种组合。题目给的 n 范围是 1 到 20所以最坏情况下 2 的 20 次方约等于 104 万。这个数量级在本地跑还能接受但放在力扣的测试环境下已经比较勉强而且如果你后面遇到 n 30 的变体2 的 30 次方超过 10 亿直接就是灾难。关键不是这道题能不能用暴力过而是它给了你一个很好的“升级台阶”。104 万次枚举本身不难难的是你从中能否提炼出重复子结构从而把指数级优化成多项式级。如果你只会 DFS 硬搜遇到 n 稍微大一点的同类题就会束手无策。还有一个很容易被忽略的难点每个元素都必须参与运算。这导致你没法直接把问题当成“找一个子集凑成某数”来想因为符号为负的数对应的是一种“反向贡献”。你需要先做一步数学转化才能把问题塞进熟悉的背包模型里。1.3 从递归树看重复子问题我们先模拟一下暴力搜索的过程。从下标 0 开始每个位置产生两条分支加上nums[i]或者减去nums[i]。走到最后一个元素时检查当前累计和是否等于target。比如nums [1, 2, 1]从(0, 0)开始第一条路径是(1, 1)第二条是(1, -1)。再往下走你很快会发现一个现象不同的符号组合可能在同一个下标位置得到相同的累计和。比如先加第一个数再减第二个数结果是(2, -1)先减第一个数再加第二个数结果也是(2, -1)。它们对应的后续搜索空间完全一样却被重复计算了两遍。这就是典型的重叠子问题。只要状态用(当前下标, 当前累计和)来表示那么无论你之前是怎么走到这个状态的从它往后能产生的合法表达式数量都是确定的。既然确定就值得缓存起来复用。想明白这一点记忆化搜索和动态规划的解法就都顺理成章了。2. 破题关键公式推导与前置条件判断2.1 把加号减号统一成数学表达式做这道题最舒服的方式是把正负号的选择重新定义一下。假设最终表达式里所有加正号的数字之和是 P所有加负号的数字它们的绝对值之和是 N。数组所有数字的总和是 sum那么一定有P N sum同时整个表达式的运算结果等于 target也就是P - N target两个式子联立把 N 消掉。由第一个式子可得N sum - P代入第二个式子P - (sum - P) target即2P - sum target所以P (sum target) / 2这一步极其关键。它把所有数字强行分正负号的问题转化成了“从数组中选出一些数让它们的和恰好等于 P一共有多少种选法”。为什么能这么转化因为一旦你确定哪些数字前面加正号剩下的数字就自动加负号方案是一一对应的。换句话说选正号集合的方案数就等于最终表达式的方案数。这就是标准的 0/1 背包计数问题每个数字只能用一次背包容量是 P求刚好装满背包的方案数。到这里题目已经从“搜索枚举”变成了“背包 DP”难度直接降了一档。2.2 sum 与 target 的奇偶性为什么 sum target 必须为偶数上面推导出了P (sum target) / 2。这个式子看起来简单里面藏着一个非常容易踩的坑P 必须是整数因为数字和背包容量都没有小数。所以sum target必须是偶数否则不可能存在任何合法表达式。举一个具体的反例nums [1, 1, 1]target 2。sum 是 3sum target 5是奇数。你手算一下也能发现三个 1 最多能表达出的结果只有 -3、-1、1、3 这几种永远凑不出 2。所以直接返回 0 就好。为什么很多人会忽略这个判断因为他们在写 DP 时会把capacity (sum target) / 2当作int处理Java 里整数相除会自动截断小数。如果sum target是奇数计算出来的 capacity 其实是向下取整后的值程序不会报错但结果就是错的。这种错非常隐蔽本地跑小用例可能碰巧对一到边界就翻车。正确做法是在开 DP 数组之前先判断if ((sum target) % 2 ! 0) { return 0; }注意这里的target可能是负数Java 的%运算在负数场景下结果也可能是负数。所以更稳妥的写法是判断((sum target) 1) ! 0或者先用Math.abs(target)做过界判断后再处理。我习惯用取模但会确保进入判断前sum target不会是负数因为如果Math.abs(target) sum已经提前返回 0 了。2.3 边界约束|target| sum 时直接返回 0还有一个前置条件很容易想到假设所有数字都加正号表达式结果最大就是 sum假设所有数字都加负号结果最小就是 -sum。所以 target 的绝对值如果大于 sum那么无论如何组合结果都不可能到达 target直接返回 0。这个判断必须放在奇偶性判断之前原因很现实如果 target 是 -100sum 是 5sum target -95除以 2 得到负数 capacity后面开数组要么抛异常要么得到错误答案。所以先判断绝对值是否越界能顺带避免负容量的坑。综合起来开 DP 之前的完整前置代码就是int sum 0; for (int num : nums) { sum num; } if (Math.abs(target) sum) { return 0; } if ((sum target) % 2 ! 0) { return 0; } int capacity (sum target) / 2;到这一步问题已经被压缩成一个纯粹的“选子集凑容量”问题。接下来就是从三种解法里挑一个实现。3. 三种解法层层递进从回溯到 DP3.1 解法一DFS 回溯搜索先拿到暴力解先写个最直接的 DFS逻辑很简单从左往右扫描数组每个位置分别尝试加号和减号走到末尾时判断累计和是否等于 target。代码如下class Solution { private int count 0; public int findTargetSumWays(int[] nums, int target) { dfs(nums, target, 0, 0); return count; } private void dfs(int[] nums, int target, int index, int currentSum) { if (index nums.length) { if (currentSum target) { count; } return; } dfs(nums, target, index 1, currentSum nums[index]); dfs(nums, target, index 1, currentSum - nums[index]); } }这段代码的时间复杂度是 O(2^n)空间复杂度主要是递归栈 O(n)。n 20 的时候最坏情况要递归 104 万次左右力扣上其实也能过但耗时在几百毫秒上下徘徊不算健康。我个人不推荐一上来就交这个版本但强烈建议把它写一遍。为什么因为它能帮你验证自己对题意的理解。写完跑几个例子确认结果正确之后再逐步优化这样每一步都有参照物。如果直接背 DP 模板错了都不知道错在哪。这个版本还有个隐患递归深度最大是 n20 层没问题但如果面试官把 n 改成 1000递归栈直接爆掉。所以回溯只能作为理解工具不能作为最终方案。3.2 解法二递归加记忆化去掉重复计算既然前面已经分析出存在重叠子问题那就用一个缓存表记录(index, currentSum)对应的方案数。每次进入递归时先查缓存如果命中直接返回结果。用 Java 实现时最直观的缓存结构是HashMap键可以用字符串index , currentSum也可以把index和currentSum打包成一个 Long。字符串可读性最好缺点是拼接有开销Long 键效率稍高但不直观。我建议刷题阶段用字符串面试手写时用二维数组或 Long 键区别不大。代码实现如下class Solution { public int findTargetSumWays(int[] nums, int target) { MapString, Integer memo new HashMap(); return dfs(nums, target, 0, 0, memo); } private int dfs(int[] nums, int target, int index, int currentSum, MapString, Integer memo) { if (index nums.length) { return currentSum target ? 1 : 0; } String key index , currentSum; if (memo.containsKey(key)) { return memo.get(key); } int add dfs(nums, target, index 1, currentSum nums[index], memo); int sub dfs(nums, target, index 1, currentSum - nums[index], memo); memo.put(key, add sub); return add sub; } }这样做的好处是每个(index, currentSum)状态只被计算一次。状态总数约为 n 乘以可能的累计和范围所以时间复杂度降到 O(n * sum)。对于 n 20、sum 最多 20000 的题设这个复杂度非常轻松。需要注意一个细节currentSum可能是负数。如果你想把 memo 换成二维数组第二维的下标就不能直接用currentSum而是要做偏移。比如累计和的范围是[-sum, sum]你可以把它映射到[0, 2*sum]用currentSum sum作为数组下标。这个偏移技巧在动态规划里同样常用后面我还会专门展开。3.3 解法三用 0/1 背包把数组“选”出来记忆化搜索已经很快了但它本质上还是递归。能不能改成自底向上的迭代 DP当然可以这就是背包方案数的经典写法。还记得前面推出的结论吗我们要从数组里选一些数字让它们的和等于capacity (sum target) / 2问有多少种选法。定义dp[i][j]表示处理完前 i 个数字时能凑出和 j 的方案数。那么状态转移就只有两个来源不选第 i 个数字方案数是dp[i-1][j]选第 i 个数字如果j nums[i-1]方案数是dp[i-1][j-nums[i-1]]。所以转移公式是dp[i][j] dp[i-1][j] (j nums[i-1] ? dp[i-1][j-nums[i-1]] : 0)先写一个清晰的二维版本方便对照int n nums.length; int[][] dp new int[n 1][capacity 1]; dp[0][0] 1; for (int i 1; i n; i) { int num nums[i - 1]; for (int j 0; j capacity; j) { dp[i][j] dp[i - 1][j]; if (j num) { dp[i][j] dp[i - 1][j - num]; } } } return dp[n][capacity];二维版本的优点是一目了然不容易出错。缺点是需要 O(n * capacity) 的空间capacity 最大可能到 10000 左右n 是 20其实也不大但既然可以优化为什么不做观察转移公式第 i 行的值只依赖第 i-1 行。因此可以用一维数组滚动更新把空间压到 O(capacity)。这也是面试时更常考察的版本class Solution { public int findTargetSumWays(int[] nums, int target) { int sum 0; for (int num : nums) { sum num; } if (Math.abs(target) sum) { return 0; } if ((sum target) % 2 ! 0) { return 0; } int capacity (sum target) / 2; int[] dp new int[capacity 1]; dp[0] 1; for (int num : nums) { for (int j capacity; j num; j--) { dp[j] dp[j - num]; } } return dp[capacity]; } }以示例nums [1, 1, 1, 1, 1]target 3来手动验证。sum 5capacity (5 3) / 2 4。问题变成“从 5 个 1 中选出若干个使和为 4 的方案数”显然是从 5 个元素里选 4 个C(5, 4) 5。代码跑出来 dp[4] 也确实是 5。这就验证了公式和 DP 实现的一致性。4. Java 实现细节与踩坑记录4.1 一维滚动数组为什么必须倒序遍历背过背包模板的同学都知道0/1 背包一维优化的核心是内层循环要倒序。但很多人只记住了“要倒序”没想明白“为什么”。这里我用一个超小例子讲透。假设nums [2]capacity 2dp 初始化是[1, 0, 0]。正序遍历时j 从 0 到 2j 00 2不成立跳过j 11 2不成立跳过j 2dp[2] dp[0]dp[2] 1。正序在这里也能得到正确结果因为有且只有一个数字。再看nums [2, 2]capacity 4。正序遍历第一个 2 后dp 变成[1, 0, 1, 0, 0]。处理第二个 2 时如果 j 正序 0 到 4j 2dp[2] dp[0]dp[2] 2j 3dp[3] dp[1]还是 0j 4dp[4] dp[2]此时 dp[2] 已经是 2所以 dp[4] 2。可正确答案应该是什么两个 2 都用上才凑出 4方案数是 1。正序算出了 2因为它把同一个数字“第二个 2”用了两次既把它当作放在 j2 时的备选又把它当作 j4 时的上一次结果。这就是典型的完全背包行为。倒序遍历时j 从 4 到 0dp[4] 读取的是还没被当前数字更新过的 dp[2]结果就是 1正确。所以记住看到一维背包内层必须倒序如果正序就是允许每个物品无限次使用适用于完全背包而不是这道题。4.2 dp[0]1 的含义与数组中有 0 的情况初始化时dp[0] 1表示凑出和为 0 有一种方案也就是一个数都不选。这个初始化不对的话后面所有结果都是 0。但有一个特殊情况容易让人怀疑人生数组里出现 0。比如nums [0, 0, 1]target 1。sum 1capacity 1。跑一遍一维 DP初始 dp [1, 0]处理第一个 0内层倒序 j 从 1 到 0j 1dp[1] dp[1]还是 0j 0dp[0] dp[0]dp[0] 2处理第二个 0j 1dp[1] dp[1]0j 0dp[0] dp[0]dp[0] 4处理 1j 1dp[1] dp[0]所以 dp[1] 4。最终答案是 4。手动验证一下[0, 0, 1]要凑出 1两个 0 各自可以取正号或负号有 4 种组合每个组合里 1 都取正号正好 4 种表达式。这说明什么0 虽然不影响和但会影响“选或不选”的方案数DP 会把这种影响通过 dp[0] 的翻倍自然计算进去。看到答案翻倍不要慌那是在正确计数。如果你在纸面推导时发现 dp[0] 越来越大这不是 bug而是 0 的特殊贡献。理解了这一点面试时被问到“如果数组里有 0 会怎样”就能从容应对。4.3 负数下标问题记忆化搜索中的偏移映射记忆化搜索版本里currentSum可能是负数。如果你不想用HashMap做缓存而是用二维数组加速就需要处理负数下标。最简单的方式是偏移累计和的范围是[-sum, sum]给它整体加上sum映射到[0, 2*sum]。int offset sum; int[][] memo new int[n][2 * sum 1]; for (int[] row : memo) { Arrays.fill(row, -1); }搜索时访问memo[index][currentSum offset]。这样每个状态都落在数组范围内。为什么不直接currentSum当下标因为 Java 数组下标必须是非负数直接访问负下标会抛ArrayIndexOutOfBoundsException。这里有一个面试加分点用偏移之前一定要确认sum target的奇偶性和大小否则 offset 可能没覆盖到所有currentSum的可能取值。比如 target 极端接近 sumcurrentSum的最大值就是 sum偏移后是2*sum数组长度必须开到2*sum 1。4.4 运算精度与溢出问题题目里nums[i]最大是 1000n 最大是 20所以 sum 最大是 20000int 完全够用。target范围是 -1000 到 1000sum target也不会溢出。但如果面试官把题设改大比如 n 到 1000nums[i]到 10^9sum就会超过 int 范围。这时候建议直接用long接收 sum 和 capacity。还有一个细节(sum target) / 2可能会得到负数吗在前面已经用Math.abs(target) sum拦截过所以不会。但如果你把代码顺序写反先算 capacity 再做绝对值判断就可能出现 capacity 为负数然后new int[capacity 1]直接抛NegativeArraySizeException。这个异常非常明显但也说明边界判断顺序很重要。长期刷题养成的习惯是所有涉及“一半”的题目都要先想清楚边界和奇偶性。很多 DP 题错得莫名其妙不是转移写错而是前置条件没判断。5. 常见问题与面试追问速查5.1 高频报错与排查我把这道题比较容易踩的坑整理成了一张速查表排错时可以直接对照症状可能原因解决方法NegativeArraySizeExceptioncapacity 是负数target 绝对值大于 sum 时没拦截先做Math.abs(target) sum判断再算 capacity结果总是偏大一维数组内层循环正序遍历内层从 capacity 往 num 倒序更新结果总是 0dp[0] 初始化为 0或者 memo 填充值不对dp[0] 必须为 1memo 初始值必须和合法方案数区分开传入普通负数 target 时答案错误sum target是奇数时没有前置拦截加上(sum target) % 2 ! 0判断数组含 0 时答案和自己手算不一致没意识到 0 会让方案数翻倍用纸笔跑一遍[0,0,1]确认翻倍是正确行为记忆化搜索时数组越界currentSum 为负数直接当下标加 offset 偏移或者改用 HashMap你可以把这几个症状当成自测用例来写[1,1,1,1,1], target3期望 5[1], target2期望 0[0,0,1], target1期望 4[1,0], target1期望 2。能一次跑对这四组基本就稳了。5.2 面试官常问的三个变体这道题的变体非常多面试官一般不会只满足于你会写模板而是会往下追问。我总结三个最高频的第一个变体如果数组里可以有负数怎么办这题本身限定了非负数组。一旦出现负数公式P (sum target) / 2就不成立了因为 sum 不再是简单的绝对值和P 和 N 的定义也会混掉。这时候得老老实实回到记忆化搜索或者用更通用的状态定义。第二个变体如果每个数字可以被重复使用怎么改这就是把 0/1 背包改成完全背包一维数组内层循环从正序开始即可。思路不变区别只在遍历顺序。面试官问这个是在考察你懂不懂倒序的真正原因。第三个变体如果不仅要方案数还要输出所有具体表达式怎么办那就得回溯收集路径DP 只负责算数量不负责记录过程。可以在 DP 的基础上再加一个路径搜索复杂度会指数上升但能够验证你对整个状态空间的理解。这种“先公式转化再套背包模型”的思考链条比背模板重要得多。你把 494 吃透前面说的 416 分割等和子集、1049 最后一块石头的重量 II 都会顺手很多。5.3 同类题型速查表刷题到最后拼的是归纳能力。我把和 494 思路相近的题整理了一张速查表题目核心特征转化思路416. 分割等和子集问能否分成两个和相等的部分转化为能否找到子集和 sum/2判断 true/false1049. 最后一块石头的重量 II问碎石后最小可能重量转化为找最接近 sum/2 的子集和求最小值494. 目标和问加正负号后等于 target 的方案数转化为找子集和 P 的方案数474. 一和零问最多能拼出多少个字符串变成二维容量背包dp 存最大个数这几道题的核心状态都是“当前元素处理到哪 当前累计容量”区别只在目标是求可行性、最大价值还是方案数。494 属于“方案数”这一类dp 的转移用的是加法而不是Math.max这是区分点。最后说点我自己的感受我在刷这道题时第一次用的是回溯提交通过之后还挺得意后来才发现根本没理解透彻。真正让我开窍的是那个公式推导把正负号问题变成选子集问题。从那时起我遇到类似的题目都会先想一步“能不能把目标值做一下数学变换让它变成容量”。建议大家不要一上来就背背包模板先把回溯版写出来再逐步改成记忆化和递推版。这个过程本身就是一次“从指数级到多项式级”的思维训练比直接看答案有意义得多。最后随手分享一个小技巧如果你总是记不住内层循环该正序还是倒序就想“0/1 背包里每个物品只能用一次所以要保证更新 dp[j] 时用到的是旧值倒序能让右边的旧值不被当前物品污染”。每次写之前默念一遍这句话比死记硬背可靠得多。