这道题我第一次在力扣上刷到的时候说实话有点懵。给你一个非负整数数组 nums每个数字前面你可以选择加 或者加 -要求最后整个表达式的计算结果恰好等于目标值 target让你返回一共有多少种不同的构造方式。LeetCode 494 这道题官方叫“目标和”我用 Java 做了一遍才发现这题背后藏着的门道比表面看起来多得多——它既可以用 DFS 暴力解也可以用记忆化搜索优化最优解还能转化成经典的 01 背包动态规划。如果你刷题刷到一定阶段会发现这题是“从回溯到动态规划”的绝佳跳板吃透它你对“什么时候该用 DP”“怎么把暴力搜索优化成 DP”这个问题会有一个质的提升。这篇文章我把自己的完整思考过程和 Java 实现都写下来适合正在刷力扣备战面试、或者刚学完动态规划想找经典题目练手的同学。1. 题目到底在问什么目标和问题的本质1.1 先把题目翻译成大白话力扣 494 的题面很简短给定一个非负整数数组nums和一个整数target你需要在每个整数前添加或-构造一个表达式使得这个表达式的运算结果等于target返回能够构造出的表达式总数。先别急着上手写代码咱们把题目的“人话版本”捋一遍。假设nums [1, 1, 1, 1, 1]target 3你可以构造出-11111 3也可以构造出1-1111 3等等总共 5 种方式。所以这不是在问“能不能凑出来”而是问“有多少种不同的加减组合能凑出来”。每一种组合本质上就是给数组里的每个元素分配一个符号二选一正号或者负号。我见过不少朋友一上来就想用排列组合硬算但数组长度最长能到 20暴力枚举 2 的 20 次方就是 104 万勉强能跑如果题目再把长度放宽到 30那就是 10 亿级别直接爆炸。所以这道题的真正考点就是看你能不能从“枚举所有方案”的死胡同里跳出来找到更优的数学结构。1.2 为什么这题能成为“经典”三种解法的演进逻辑这道题之所以被这么多面试官青睐不是因为它难到天上去而是因为它恰好踩中了算法学习的三个关键台阶。第一个台阶是 DFS 回溯。这是最直觉的思路——把每个数字的正负号都试一遍递归到数组末尾如果累加和等于 target就计入答案。优点是容易理解缺点是纯指数级复杂度只适合作为“暴力基准”。第二个台阶是记忆化搜索。你会在 DFS 的过程中发现大量子问题被重复计算了。比如处理到下标 i、当前累加和为 sum 这个状态可能在多条不同路径上都会遇到那不如用哈希表把这个状态的结果存下来下次直接查表。这一步让复杂度从 2 的 n 次方降到了 O(n * sum) 量级是不改变思路框架的“纯优化”。第三个台阶是动态规划。这是最优解的核心思路也是这道题真正的精华所在。你需要把“加正号还是负号”这件事情做一个数学变形最终把问题转换成“从数组里选出若干个数使其和等于某个定值”这就是 01 背包求方案数的标准模型。能自己推到这个阶段的人说明对动态规划的理解已经脱离了“背模板”的阶段。我在实际刷题和面试复盘里反复体会到这三步恰好对应了一个程序员面对算法题时的正常心智过程先暴力再优化最后寻找更优模型。所以写这篇题解的时候我决定把三条路都走一遍而不是只贴一个最优解——只有把演进过程看清楚了你才能真正理解 DP 版本里那两行关键的等式是怎么来的。2. 解法一与解法二回溯 DFS 和记忆化搜索的 Java 实现2.1 朴素回溯先跑通再说先把最直白的 DFS 代码亮出来。我用一个全局计数器来统计满足条件的表达式数量每次递归决定当前数字取正还是取负然后把下标往后移一位。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]); } }这段代码的逻辑很简洁从第 0 个元素开始每一层递归都有两个分支正号和负号等递归到数组末尾时检查当前和是否等于目标值。你如果自己跑一遍会发现它能通过示例但效率惨不忍睹——时间复杂度是 O(2^n)空间复杂度是 O(n) 的递归栈深度。这里我特别想提醒一个细节count作为成员变量在 LeetCode 的判题环境里每次调用findTargetSumWays前都会被重置因为每个测试用例都是新建一个Solution对象一般不会出问题。但如果你在本地写测试代码反复调用同一个Solution实例的findTargetSumWays就会踩坑——count累积了上一次的结果。所以我建议不要在成员变量上依赖隐式重置而是把计数器作为递归函数的返回值或者每次进入方法先清零。这个小细节虽然不影响 LeetCode 提交但对面试时写代码的严谨性是有加分的。2.2 记忆化搜索给 DFS 装上缓存如果你跑过朴素 DFS 的性能会看到大量的重复计算。举个具体例子nums [1, 1, 1]的时候先走1, 1到达 index 为 2、sum 为 2 的状态和先走1, -1再在某条路径上到达 index 为 2 且 sum 为 2 的状态这两个子问题其实一模一样——从 index 为 2 开始当前累计和是 2剩下能产生的方案数是固定的。但 DFS 没有记性它会把这个子问题在不同路径上反复展开。解决办法就是用缓存。关键状态由两个维度决定当前处理到的下标index以及当前累计和sum。我们用MapString, Integer把index , sum作为 key映射到“从这个状态出发还能构造出多少种合法方案”。在递归返回前把结果存进去下次再遇到同一个 key直接取值返回。import java.util.HashMap; import java.util.Map; class Solution { public int findTargetSumWays(int[] nums, int target) { // key: index,sumvalue: 从该状态出发可得到的方案数 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 ways dfs(nums, target, index 1, currentSum nums[index], memo) dfs(nums, target, index 1, currentSum - nums[index], memo); memo.put(key, ways); return ways; } }我第一次写记忆化搜索的时候用的 key 是直接把index和sum拼成字符串这在数组元素少的时候没问题但字符串拼接在大数据量下还是有一点额外开销。更优雅的做法是用一个二维数组当缓存行数等于nums.length 1列数覆盖所有可能的当前和范围。因为所有数字的总和是有限的currentSum的取值范围会在[-totalSum, totalSum]之间用偏移量totalSum把负数下标映射到数组的正区间就行。这就是记忆化搜索的“数组版”实现代码上比哈希表稍微绕一点但性能更好。这个版本的时间复杂度是 O(n * sum)因为每个(index, sum)状态最多被计算一次而状态总数大约是 n 乘以和的范围宽度。相比朴素 DFS 已经是指数级到多项式级的飞跃。但面试官看到这里通常还会追问一句“能不能用动态规划做”接下来我们要讲的就是这道题真正的重头戏。3. 最优解核心如何把“加加减减”变成 01 背包问题3.1 关键数学推导P (sum target) / 2 是怎么来的从记忆化搜索到动态规划中间的桥梁是一步非常漂亮的数学变形。我们设所有取正号的数字之和为 P所有取负号的数字绝对值之和为 N那么整个数组的元素总和就是sum P N。而题目要求构造出的表达式的值为 target也就是P - N target。注意这里有两个等式P N sumP - N target两式相加得到2P sum target也就是P (sum target) / 2这一步是整个 DP 解法的灵魂。它告诉我们只要能从数组中选出若干个数使其和等于 P那么这些选中的数字在表达式中就应该取正号其余数字取负号最终结果必然等于 target。问题从“决定每个元素是正还是负”转化成了“选哪些元素构成一个和为 P 的子集”。这就是标准的“恰好装满容量为 P 的背包求方案数”问题。这里有两个前置条件必须检查。第一个是sum target必须是非负偶数否则 P 不是整数直接返回 0。第二个是 P 不能超过 sum否则选不出这样的子集。很多人在 LeetCode 上提交 WAWrong Answer就是因为漏了奇数条件的判断这种情况尤其容易出现在target是负数或者sum target是奇数的测试用例里。我在本地调试的时候专门测过nums [1]、target 2和nums [1]、target -3这两个边界都会因为这两个条件被直接拦下来省了不少时间。3.2 用 01 背包的视角重新理解问题01 背包问题的本质是有一堆物品每件物品重量不同你有一定的背包容量问能装下多少种组合。在这道题里“物品”就是数组里的每个元素“重量”就是元素值本身“背包容量”就是我们刚算出来的 P“组合数”就是最终答案。而且每件物品只有选取正号和不选取负号两种状态完全吻合 01 背包的“每件物品只能取一次”的设定。这里我要特别说一下“方案数”和“最大价值”的区别。经典 01 背包求的是“容量内能装的最大价值”而这道题求的是“恰好凑出容量 P 的方案数量”所以动态规划数组里存的不是最大价值而是方案数。这是个很容易被惯性带偏的地方——我见过不少朋友把 01 背包模板的dp[j] max(dp[j], dp[j - weight] value)直接套过来结果答案变成了 0 和 1 的某种奇怪结果。方案数背包的转移方程应该是dp[j] dp[j] dp[j - nums[i]]含义是“不取当前元素刚好凑出 j 的方案数”加上“取当前元素先凑出 j - nums[i]再放入当前元素凑满 j 的方案数”。这两种情况互斥且完备相加就是不重复不漏的完整方案数。一个很重要的初始化细节是dp[0] 1因为凑出容量 0 的方案只有一种——什么都不选。其他位置初始化为 0。这个初始化的正确性很多人想不明白我可以给个直观解释容量 j 能从 0 一点点累加上来全靠dp[0]作为种子。比如第一个元素是 2执行dp[2] dp[0]dp[2]因此变成 1表示“选元素 2 凑出容量 2”的方案存在。如果dp[0]是 0整个递推全盘归零。4. 动态规划 Java 实现从二维到一维的完整过程4.1 二维 DP先看懂再谈优化为了把转移逻辑看得清清楚楚我们先写一个二维版本。dp[i][j]表示从前 i 个元素中选恰好凑出和 j 的方案数。状态转移分两种情况当前元素大于 j 时只能不选当前元素小于等于 j 时可以选也可以不选。class Solution { public int findTargetSumWays(int[] nums, int target) { int sum 0; for (int num : nums) { sum num; } // 剪枝不满足数学条件直接返回 0 if (sum target || (sum target) % 2 ! 0 || (sum target) 0) { return 0; } int capacity (sum target) / 2; int[][] dp new int[nums.length 1][capacity 1]; dp[0][0] 1; for (int i 1; i nums.length; i) { for (int j 0; j capacity; j) { // 默认不选第 i 个元素 dp[i][j] dp[i - 1][j]; // 如果容量够还能加上“选第 i 个元素”的方案 if (j nums[i - 1]) { dp[i][j] dp[i - 1][j - nums[i - 1]]; } } } return dp[nums.length][capacity]; } }这段代码里有个细节值得琢磨为什么内层循环要从 0 遍历到 capacity而不是像很多模板那样从 capacity 倒着到 0因为二维数组里的dp[i]这一行是完全基于dp[i-1]计算出来的这里没有“原地覆盖”的问题正序、倒序都不会污染数据。你甚至可以理解为先把上一行的值“拷贝”下来再额外累加“取当前元素”的部分。我建议所有刚开始学 DP 的同学先把这个版本跑通。它的可读性最好数组里的每个格子都能对应到具体场景。比如dp[2][3]就表示前两个元素中选出若干个凑成 3 的方案数调试的时候打印整个二维数组你能一眼看出递推过程有没有问题。4.2 一维滚动数组正式提交的优雅写法二维版本的缺点很明显——空间复杂度是 O(n * capacity)如果数组总和很大这个二维数组会吃掉不少内存。而且我们仔细看转移方程会发现dp[i][j]只依赖dp[i-1][...]这一行更早的行根本用不到了。所以我们可以只保留一行在当前行上原地更新这就是滚动数组。但这里有一个致命细节内层循环必须从 capacity 倒序遍历到当前元素的值。为什么因为如果我们正序更新dp[j]用的是当前这一轮已经更新过的新值而新值可能已经包含了“当前元素被用了一次”的方案继续累加就会导致同一个元素被使用多次从 01 背包变成了完全背包方案数会被严重算多。倒序遍历则保证每个元素只被考虑一次。class Solution { public int findTargetSumWays(int[] nums, int target) { int sum 0; for (int num : nums) { sum num; } // 边界条件一网打尽target 绝对值超过 sum 不行sum target 为奇数或负数不行 if (sum Math.abs(target) || (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]; } }你看这个最终版多么干净十几行代码就搞定了。遍历每个元素的时候倒序更新 dp 数组转移方程只有一行dp[j] dp[j - num]。这里我还悄悄做了一点优化把边界判断合并成sum Math.abs(target) || (sum target) % 2 ! 0。Math.abs(target)这个写法一次性覆盖了 target 为负数且绝对值大于 sum 的情况比单纯写sum target更严谨因为如果 target 是 -5 而 sum 是 3sum target不成立但sum Math.abs(target)是 3 5直接拦下。这是我踩过坑之后自己加的保险。有个面试时表现很好的延伸思考为什么最后返回的是dp[capacity]因为在容量恰好为 P 的位置存储的就是“从整个数组中选出若干元素恰好凑出 P”的总方案数而这恰恰就是原题中所有能构成 target 的加减方案的数目。从集合论角度看我们做的是一个双射映射——每个“取正号”元素集合对应唯一一种加减表达式反过来每种表达式也唯一对应一个“取正号”元素集合。所以两者数量必然相等。5. 实测对比与踩坑实录易错细节全排查5.1 数组里的 0 到底怎么处理这是这道题最阴险的一个陷阱。如果nums [0, 0, 1]target 1直观想两个 0 前面既可以放正号也可以放负号完全不影响最终结果所以 0 的存在会成倍增加方案数。我自己第一次跑这个用例的时候答案直接比预期少了排查了半天才发现问题出在“0 是否被当成普通元素参与背包”。看代码逻辑会更有画面感。一维 dp 中如果num 0倒序遍历时dp[j] dp[j - 0]等价于dp[j] dp[j]也就是每一轮都把dp[0]到dp[capacity]的值全部翻倍。这其实是对的——因为每个 0 都有“取正号”和“取负号”两种等价选择每个 0 的加入会让所有方案数翻倍。但二维版本可能不会自动做到这一点如果你沿用“如果不选就是dp[i][j] dp[i-1][j]”的逻辑再额外加“如果容量够还得加上选了它的方案”j 0恒成立所以确实会执行dp[i][j] dp[i-1][j]最终就是翻倍。关键是内层循环不能把j 0排掉。很多人写循环时习惯从 1 开始遍历容量这样就漏掉了 0 对方案数的影响结果当然不对。5.2 一维 DP 的内层循环顺序写反就变完全背包我在 4.2 已经强调过倒序遍历的原因但这里还想提供一个反例帮你加深记忆。假设nums [1, 2]capacity 2如果内层正序遍历处理 num1 时dp[1] 变成 1dp[2] 再加上 dp[1] 变成 1。处理 num2 时dp[2] 再加上 dp[0] 变成 2。看起来最终答案 2好像还挺对但把数据改成nums [1, 1]capacity 2正序遍历会得到 dp[2] 2而正确答案应该是 1——只有选两个 1 这一种方案。正序遍历时第一个 1 处理完dp[1]1处理第二个 1 时j2 时dp[2] dp[1]此时 dp[1] 已经是 1再加一次原来是 0 的 dp[2]得到 1然后 j1 时dp[1] dp[0]dp[1] 变成 2。但这不对啊正确答案应该是 dp[2]1。这个例子其实完美展示了正序污染——dp[1] 被更新成 2说明“数字 1”这个元素在里面被用了不止一次。所以背下“01 背包倒序遍历完全背包正序遍历”这句话的同时也要亲手跑一遍这个反例才能真正建立起条件反射。5.3 边界条件速查表我把实际提交中容易触发的边界条件整理成一个速查表建议你刷题时把这些 case 当成必测项测试用例预期结果原因与解释nums[1], target20sum1 abs(target)2直接剪枝nums[1], target-30同上绝对值超过总和nums[1,1,1,1,1], target35LeetCode 官方示例验证基本逻辑nums[1], target11只有一个元素时选它即可nums[1,2,1], target02sum4capacity2选 [2] 或 [1,1] 两种nums[0,0,1], target14两个 0 各有两种符号2*24 种nums[0], target02空集和 {0} 都对应同一种实际结果但符号组合有 2 种最后一行nums[0], target0是个很有意思的哲学题空集不选任何元素表达式为0满足条件选 0 且取正号表达式是0也满足选 0 且取负号表达式是-0还等于 0所以一共三种不对等一下。实际上 {0} 这个子集对应取正号空集对应不选 0而“取负号的 0”并不是一个不同的子集——因为在转化后的子集和问题里我们只区分“选进 P 集合”和“没选进 P 集合”符号的选择完全由集合决定。所以nums[0], target0时capacity (00)/2 0背包容量为 0只有空集一种选法但每个 0 元素可以自由取正负吗这里又重新涉及 0 的翻倍问题。实际上如果用上面的一维代码跑第一个元素 num0倒序遍历j0到0dp[0] dp[0]dp[0] 变成 2所以返回 2。这个结果和 LeetCode 判题是一致的[0]、target0的输出是 2。要理解这里的“2”必须回到原题——元素 0 前可以放加号或减号但两种表达式计算值都为 0所以计数为 2。子集和模型在 0 元素面前暴露了自己的局限它只区分“选/不选”而 0 的“选”和“不选”在数值上等价但符号层面“选 0 为正是选选 0 为负其实等于不选”所以子集和模型对 0 的处理必须推回到 dp 递推的翻倍逻辑才能得到正确答案。这也是为什么我说“0 是这道题最大的隐藏考点”面试官特别爱拿它来验证你是否真正理解模型的适用范围而不只是背了代码。5.4 其他高频坑位汇总除了上面三个大坑我把自己刷题时踩过的其他小坑也列在下面不一定致命但都很影响调试心情。递归写法中超时如果面试时你先写 DFS 给面试官看思路记得主动提一句“这个解法在 n30 时会超时所以需要优化”展现你的复杂度意识比闷头改进代码效果更好。capacity计算时用(sum target) / 2很多语言里负数除法是向零取整的所以要先用取模判断奇偶性再除不迟。数组元素非负但可能为 0j num这个条件对 num0 时是j 0内层循环必须正常进入不能写成j 0。一些 Java 实现里习惯用Integer缓存结果但方案数可能超过Integer.MAX_VALUE吗看题目约束LeetCode 保证答案在 32 位带符号整数范围内所以 int 够用。但如果你自己扩展题目不设上限就得用 long 甚至 BigInteger。如果target是负数capacity有可能算出来是负数吗不会因为sum target非负且偶数capacity 自然非负。但 capacity 为 0 时数组长度要至少为 1代码里dp[0]1之后循环仍然正常执行逻辑没毛病。6. 面试场景下的追问与扩展从一题到一类6.1 面试官问“还有其他解法吗”怎么答这类问题在面试里很常见。如果你已经给出 DP 解面试官还可能追问三种变体第一怎样求“具体方案”而不只是方案数这就要在 DP 的基础上回溯收集所有满足条件的路径。你可以新增一个boolean类型的辅助数组记录每个容量在每个元素处是否可以选择该元素然后从dp[capacity]反推回去输出所有路径。复杂度会高一些但思路很自然。第二如果数组元素不是非负而是有正有负模型还成立吗这时候P - N target的推导仍然成立但“选若干元素使其和等于 P”变成了有负数的子集和问题普通的 01 背包模板不能直接处理。需要把所有数加上偏移量转成正数或者改用 DFS状态压缩。这属于进阶扩展面试能说出来通常会很加分。第三如果target特别大接近sum甚至超过sum怎么办直接剪枝返回 0 就是最优策略这也是我们边界判断的实际意义。6.2 从这道题延伸出的同类题清单我把“目标和”归入“子集和问题家族”这个家族在 LeetCode 上有很多亲戚。做完 494 之后建议你顺手把下面几道题一起刷了416 分割等和子集判断数组能否被分割成两个和相等的子集本质上就是容量为sum/2的 01 背包可行性问题。322 零钱兑换完全背包求最小数量和 01 背包对照着看你会发现遍历顺序的差异直接决定物品能不能重复用。518 零钱兑换 II完全背包求方案数和 494 的“01 背包方案数”对比能加深对两类背包模型的理解。1049 最后一块石头的重量 II这题本质上也是把数字分成两堆求最小差和 494 的数学变形殊途同归。如果你把这些题放在一起研究会发现它们全都是“选或不选”这个基础决策模型的变体。区别只在于目标函数是“最大价值”“最小数量”还是“方案数”。能把这一层看清楚动态规划的很多题目在你眼里就不再是一道一道孤立的题而是相互连成了一张网。6.3 我刷这题的真实心得最后聊聊个人体验。我第一次做 494 是在准备面试的阶段当时已经会背 01 背包模板了但看到“目标和”这三个字完全没意识到跟背包有关系老老实实写了 DFS 然后超时。后来看了别人的题解被P (sum target) / 2这一步惊艳到了才真的体会到“算法题考的是数学观察”这句话是什么意思。从那以后我养成了一个习惯遇到任何动态规划题先把“朴素搜索的状态”写出来然后问自己三个问题——状态有几个维度能不能合并维度转移方程里有没有重复计算这三个问题顺着捋下来很多 DP 的状态设计就水到渠成了。494 这道题就是标准的“DFS 状态是 index 和 currentSum通过数学变换扔掉 index 维度变成只依赖容量的一维背包”。如果你现在刷题还停留在“看懂题解就下一题”的阶段我强烈建议你停下来把 494 按照“暴力 DFS - 记忆化搜索 - 二维 DP - 一维 DP”这个顺序亲手敲一遍。每步都打印几个中间状态对比一下你对“为什么一维要倒序”“为什么 dp[0] 等于 1”“为什么 0 元素会翻倍”的理解一定会比看十篇文章都牢固。这道题值得你花一整个晚上慢慢啃因为啃下来的不只是这一题的解法而是一整套把暴力搜索优化成动态规划的思维路径。