企业官网建设流程全解析

这道题我第一次在力扣上刷到的时候，说实话有点懵。给你一个非负整数数组 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，你可以构造出-1+1+1+1+1 = 3，也可以构造出1-1+1+1+1 = 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。我们用Map<String, Integer>，把index + "," + sum作为 key，映射到“从这个状态出发，还能构造出多少种合法方案”。在递归返回前，把结果存进去；下次再遇到同一个 key，直接取值返回。

import java.util.HashMap; import java.util.Map; class Solution { public int findTargetSumWays(int[] nums, int target) { // key: "index,sum"，value: 从该状态出发可得到的方案数 Map<String, Integer> memo = new HashMap<>(); return dfs(nums, target, 0, 0, memo); } private int dfs(int[] nums, int target, int index, int currentSum, Map<String, 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 = sum
• P - N = target

两式相加，得到2P = sum + target，也就是：

P = (sum + target) / 2

这一步是整个 DP 解法的灵魂。它告诉我们：只要能从数组中选出若干个数，使其和等于 P，那么这些选中的数字在表达式中就应该取正号，其余数字取负号，最终结果必然等于 target。问题从“决定每个元素是正还是负”转化成了“选哪些元素构成一个和为 P 的子集”。这就是标准的“恰好装满容量为 P 的背包，求方案数”问题。

这里有两个前置条件必须检查。第一个是sum + target必须是非负偶数，否则 P 不是整数，直接返回 0。第二个是 P 不能超过 sum，否则选不出这样的子集。很多人在 LeetCode 上提交 WA（Wrong 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 是 3，sum < 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，如果内层正序遍历：

• 处理 num=1 时，dp[1] 变成 1，dp[2] 再加上 dp[1] 变成 1。
• 处理 num=2 时，dp[2] 再加上 dp[0] 变成 2。

看起来最终答案 2，好像还挺对？但把数据改成nums = [1, 1]，capacity = 2，正序遍历会得到 dp[2] = 2，而正确答案应该是 1——只有选两个 1 这一种方案。正序遍历时，第一个 1 处理完，dp[1]=1；处理第二个 1 时，j=2 时dp[2] += dp[1]，此时 dp[1] 已经是 1，再加一次原来是 0 的 dp[2]，得到 1；然后 j=1 时dp[1] += dp[0]，dp[1] 变成 2。但这不对啊，正确答案应该是 dp[2]=1。这个例子其实完美展示了正序污染——dp[1] 被更新成 2，说明“数字 1”这个元素在里面被用了不止一次。所以背下“01 背包倒序遍历，完全背包正序遍历”这句话的同时，也要亲手跑一遍这个反例，才能真正建立起条件反射。

5.3 边界条件速查表

我把实际提交中容易触发的边界条件整理成一个速查表，建议你刷题时把这些 case 当成必测项：

最后一行nums=[0], target=0是个很有意思的哲学题：空集不选任何元素，表达式为0，满足条件；选 0 且取正号，表达式是0也满足；选 0 且取负号，表达式是-0还等于 0，所以一共三种？不对，等一下。实际上 {0} 这个子集对应取正号，空集对应不选 0，而“取负号的 0”并不是一个不同的子集——因为在转化后的子集和问题里，我们只区分“选进 P 集合”和“没选进 P 集合”，符号的选择完全由集合决定。所以nums=[0], target=0时，capacity = (0+0)/2 = 0，背包容量为 0，只有空集一种选法，但每个 0 元素可以自由取正负吗？这里又重新涉及 0 的翻倍问题。实际上如果用上面的一维代码跑，第一个元素 num=0，倒序遍历j=0到0，dp[0] += dp[0]，dp[0] 变成 2，所以返回 2。这个结果和 LeetCode 判题是一致的：[0]、target=0的输出是 2。要理解这里的“2”，必须回到原题——元素 0 前可以放加号或减号，但两种表达式计算值都为 0，所以计数为 2。子集和模型在 0 元素面前暴露了自己的局限：它只区分“选/不选”，而 0 的“选”和“不选”在数值上等价，但符号层面“选 0 为正是选，选 0 为负其实等于不选”，所以子集和模型对 0 的处理必须推回到 dp 递推的翻倍逻辑才能得到正确答案。这也是为什么我说“0 是这道题最大的隐藏考点”，面试官特别爱拿它来验证你是否真正理解模型的适用范围，而不只是背了代码。

5.4 其他高频坑位汇总

除了上面三个大坑，我把自己刷题时踩过的其他小坑也列在下面，不一定致命，但都很影响调试心情。

• 递归写法中超时：如果面试时你先写 DFS 给面试官看思路，记得主动提一句“这个解法在 n=30 时会超时，所以需要优化”，展现你的复杂度意识，比闷头改进代码效果更好。
• capacity计算时用(sum + target) / 2，很多语言里负数除法是向零取整的，所以要先用取模判断奇偶性，再除不迟。
• 数组元素非负但可能为 0，j >= num这个条件对 num=0 时是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 元素会翻倍”的理解，一定会比看十篇文章都牢固。这道题值得你花一整个晚上慢慢啃，因为啃下来的不只是这一题的解法，而是一整套把暴力搜索优化成动态规划的思维路径。