企业官网建设流程全解析

第一次在力扣上看到494这道题，我第一反应是：这不就是枚举每个数前面是加号还是减号吗？等真正把回溯写出来跑了一遍，才发现题目名字“目标和”三个字背后，牵出来的是动态规划里非常经典的一套转化思路。力扣494，英文名Target Sum，中文名目标和，题目很直接：给你一个整数数组nums和一个整数target，给每个数字前面放上'+'或'-'，按原顺序拼成一个数学表达式，返回这个表达式结果恰好等于target的不同拼法数量。

这道题在LeetCode里被标记为Medium难度，常被归类为动态规划，但真实刷题过程中，几乎每个人都是从DFS暴力枚举开始的。问题在于，回溯虽然能通过，复杂度却是指数级的，面试官大概率不会满意。这篇文章我打算从Java实现的角度，把整条思考链路完整拆开：最直观的DFS长什么样、怎么想到数学转化成背包问题、二维DP和一维DP分别怎么写、那些边界条件到底坑在哪。适合正在准备算法面试的Java开发者，也适合刚接触背包问题的人把它当入门案例。

1. 这道题的第一眼印象：暴力回溯为什么能过却不能拿来面试

1.1 题目原貌与输入边界

先把题目完整复述一遍。给定一个非负整数数组nums，长度范围一般是1到20，每个元素的值在0到1000之间，目标值target的范围在-1000到1000之间。对于数组里的每一个数字，你只能做一个选择：要么加正号，要么加负号。比如nums=[1,1,1,1,1]，target=3，那么有5种组合方式：

• -1+1+1+1+1 = 3
• +1-1+1+1+1 = 3
• +1+1-1+1+1 = 3
• +1+1+1-1+1 = 3
• +1+1+1+1-1 = 3

所以答案是5。注意这里每个数字都必须使用，不能跳过，也就是说，每个数字前面必须且只能出现一个符号。这个约束条件决定了它天然是“二选一”的分支结构，也就天然适合用DFS去枚举。

1.2 最直觉的DFS写法

拿到这种“要么A要么B求方案数”的题，第一反应自然是深度优先搜索。我从index=0开始，每到一个位置，就尝试一次加nums[index]、一次减nums[index]，走到数组末尾时判断当前累计和是否等于target。代码非常短，几十行就能写完。

class Solution { private int count = 0; public int findTargetSumWays(int[] nums, int target) { dfs(nums, 0, 0, target); return count; } private void dfs(int[] nums, int index, int currentSum, int target) { if (index == nums.length) { if (currentSum == target) { count++; } return; } // 当前数字放正号 dfs(nums, index + 1, currentSum + nums[index], target); // 当前数字放负号 dfs(nums, index + 1, currentSum - nums[index], target); } }

这样写没问题，逻辑也一眼能看懂。从二叉树的角度看，每个节点会展开两个分支，整棵树的高度是nums.length，叶子节点数量是2的n次方。这是理解这道题复杂度的起点。

1.3 指数级复杂度的实际感受

n=15时，叶子节点32768，完全没问题；n=20时，超过100万，勉强能跑；n=30时，约10.7亿，这个量级在Java里单线程跑完需要好几秒，面试场景下基本等于超时。

LeetCode对这道题的约束通常把n压在20以内，所以回溯解法在评测机上勉强能过，但耗时可能已经到了几百毫秒甚至一秒以上，属于“能AC但很勉强”的状态。实际面试的时候，我见过不少候选人在这里直接写DFS，然后报复杂度O(2^n)。这个答案本身没错，但如果面试官追问一句“n到30怎么办”，没有后续优化的候选人通常会卡住。这也从侧面说明，DFS只是理解题意的第一步，不是这道题真正想考的终点。

1.4 为什么说这不是最理想的答案

力扣把494标成Medium，用意很明显：希望你从指数级的枚举，想到多项式级甚至线性级的动态规划。后面要讲的背包转化就是典型思路。如果只停在回溯层面，等于只做了题目的前半段。我自己刷这道题时也是先AC了回溯版本，然后看了一眼题解里的DP转化，才发现原来还有更本质的解法。从那以后，我养成了一个习惯：每道题AC之后，都会追问自己一句“有没有比枚举更聪明的办法”。

2. 从加减号到背包：sum与target的数学换算

2.1 设两个变量，把符号问题变成选数问题

假设所有加正号的数字之和是P，所有加负号的数字之和的绝对值是N。数组所有元素的总和记为sum。那么：

• P + N = sum（正号部分加负号部分，等于所有数字绝对值之和）
• P - N = target（最终表达式的结果）

把两个等式左右分别相加：

(P + N) + (P - N) = sum + target

化简得到：

2P = sum + target

所以P = (sum + target) / 2。

这个公式是整个解法的核心。它的意思很关键：我不用真的去考虑每个数字到底放正号还是负号，只需要从nums里挑出一部分数字，让它们的和恰好等于P，剩下的数字自动就归到负号那边去了。只要被选进“正号组”的数字和是P，整个表达式的结果就一定是target。

2.2 可行性检查的三个硬性前提

P=(sum+target)/2这个式子要成立，必须满足几个前提，任何一个不满足就直接返回0：

第一，sum+target必须是偶数。因为P是整数，如果sum+target是奇数，除以2就出现小数，说明不存在任何一组正负号分配能凑出target。比如nums=[1,2]，target=1，sum=3，sum+target=4，P=2，可行；但如果target=2，sum+target=5，奇数，无解。

第二，sum必须不小于Math.abs(target)。如果数组里所有数字绝对值之和都比目标值小，比如nums=[1,2]，target=10，sum=3，无论怎么分配正负号，结果最大也就是3，最小是-3，永远到不了10。这个条件用绝对值判断最稳妥，因为target本身可能是负数。

第三，P必须是非负的。当target是负数且绝对值大于sum时，上面第二个条件已经排除；当target是正数时P显然为正。所以实际代码里，先做绝对值和奇偶两个判断，P的符号问题也就一并解决了。

2.3 问题等价变体：装满容量为P的背包

经过转化，原题变成了这样：从数组nums中选出若干个数，使它们的和恰好等于P，问有多少种不同的选法。这就是标准01背包问题里的“装满容量为P的背包有多少种方案”。

这里为什么是01背包而不是完全背包？因为每个数字只能用一次。每个数字要么进正号组，要么不进正号组，不存在重复使用。这样一转化，整个题目就从“构造表达式”脱胎换骨成了“子集求和”，动态规划的思路自然就来了。

2.4 用示例验证数学推导

回到经典的输入nums=[1,1,1,1,1]，target=3。sum=5，sum+target=8，P=4。也就是说，我需要从5个1里面选出4个1，使它们的和等于4。C(5,4)=5。这和前面手动枚举出的5种表达式完全对应。

再看另一个例子：nums=[1,2,3]，target=1。sum=6，sum+target=7，是奇数，直接返回0。手动验证一下也能发现，无论怎么加正负号，得到的结果只可能是6、2、0、-2、-6、-4这些偶数，确实不可能等于1。这个验证过程建议自己动手算一遍，比单纯背公式更能理解为什么奇偶检查是必要的。

3. 动态规划递推与一维数组的倒序玄机

3.1 二维DP的状态定义与转移

定义dp[i][j]表示：只用前i个数字（i从0到nums.length），能够凑出和恰好为j的方案数。i=0时表示一个数字都不用，j的范围是0到P。

状态转移时考虑第i个数字nums[i-1]（因为i从1开始）：

• 不选它进正号组：方案数等于dp[i-1][j]，也就是前i-1个数字凑出j的方案数。
• 选它进正号组：前提是j >= nums[i-1]，此时方案数等于dp[i-1][j - nums[i-1]]。

把两种情况加起来：

dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i-1]]

这个递推式的物理意义很清晰：当前数字只有两种命运，要么被选中，要么不被选中，方案数是两条路径的和。这和回溯时每个节点分两个分支是同一个逻辑，只是用数组把重复计算的子问题缓存起来了。

3.2 初始化的含义：dp[0][0]为什么等于1

dp[0][0] = 1，意思是什么都不选，凑出的和就是0，这是一种方案。dp[0][anything else] = 0，因为不选任何数字不可能凑出非零的和。

这个初始化直接决定了整个递推的起点。很多人在这道题上犯错，就是因为把dp[0][0]写成了0，导致后面所有结果都少算。背包问题的dp[0]永远是1，这个习惯值得刻在脑子里。我自己的理解方式是：空集是一种合法的选择，它对应的方案数是1而不是0，这个1会通过递推一路传播到所有能由“空集加上若干数字”构成的子集和上。

3.3 二维DP代码示意

class Solution { public int findTargetSumWays(int[] nums, int target) { int sum = 0; for (int num : nums) { sum += num; } if (sum < Math.abs(target) || (sum + target) % 2 != 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++) { 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[nums.length][capacity]; } }

二维版本的好处是逻辑直观，不容易出错，缺点是空间复杂度O(n*capacity)。对于这道题的数据范围完全够用，但如果想追求更优空间，就得用一维滚动数组。

3.4 一维滚动数组的由来

观察二维递推式，发现dp[i][j]只依赖dp[i-1]这一行，跟更早的行没有任何关系。因此可以用一维数组滚动更新。这样dp[j] = dp[j] + dp[j - num]，其中等号右边的dp[j]在没有被当前数字更新前，保存的还是上一轮的结果，正好对应dp[i-1][j]；而dp[j - num]同理，在倒序更新时还没有被当前数字污染，对应dp[i-1][j - num]。

3.5 为什么必须倒序遍历

如果j从小到大正序遍历，问题就来了。假设num=2，当j=2时更新了dp[2]，j=4时再去读dp[2]，这时dp[2]里已经包含了“用了一次num后的方案数”，再把它加一遍，等于同一个数字被用了两次。这就不再是01背包，而是完全背包，即每个物品可以被无限取用。

我第一次写这道题的时候就是栽在这里，把内层循环写成了正序，结果遇到全零数组和适当目标值时答案成倍膨胀，怎么都对不上。后来才意识到是物品重复使用的问题。这个坑太经典了，值得单独强调：一维优化的铁律就是外层循环遍历物品，内层循环从capacity到num倒序遍历。

3.6 手推一遍递推过程

用nums=[1,1,1,1,1]，target=3来演算。sum=5，P=4，dp数组长度为5，初始化为[1,0,0,0,0]。

处理第一个1：倒序更新，dp[4]=dp[4]+dp[3]=0，dp[3]=0，dp[2]=0，dp[1]=dp[1]+dp[0]=1，得到[1,1,0,0,0]。

处理第二个1：dp[4]=0，dp[3]=0，dp[2]=dp[2]+dp[1]=1，dp[1]=dp[1]+dp[0]=2，得到[1,2,1,0,0]。

处理第三个1：dp[4]=0，dp[3]=dp[3]+dp[2]=1，dp[2]=1+3=4，dp[1]=2+1=3，得到[1,3,4,1,0]（注意这里dp[2]应该是dp[2]+dp[1]，即1+2=3，所以我更正一下，正确结果是dp[2]=3，数组为[1,3,3,1,0]）。

处理第四个1：dp[4]=dp[4]+dp[3]=1，dp[3]=1+3=4，dp[2]=3+3=6，dp[1]=3+1=4，得到[1,4,6,4,1]。

处理第五个1：dp[4]=1+4=5，dp[3]=4+6=10，dp[2]=6+4=10，dp[1]=4+1=5，得到[1,5,10,10,5]。

最终dp[4]=5，正好是C(5,4)。建议自己动手在纸上推一遍，这个过程能直观体现背包方案数的累加逻辑，比直接看代码理解深刻得多。

4. Java完整实现与边界条件清单

4.1 最终可提交的完整代码

把一维优化思路写成完整可用的Java实现：

class Solution { public int findTargetSumWays(int[] nums, int target) { int sum = 0; for (int num : nums) { sum += num; } // 目标绝对值不能大于总和 if (sum < Math.abs(target)) { return 0; } // sum + target 必须是偶数 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]; } }

这段代码时间复杂度O(n*capacity)，空间复杂度O(capacity)。capacity在最坏情况下接近sum/2，而sum最大到20000（20个数每个最大1000），所以性能没有任何压力。提交到LeetCode上，运行时间通常在2ms左右，属于第一梯队。

4.2 常见错误清单

这道题的错误集中在几个点上。

第一，忘记对target取绝对值。有些测试用例的target是负数，比如nums=[1,2,3]，target=-6，sum=6，其实答案是1，因为-1-2-3=-6。如果你用sum < target去判断，sum=6不小于-6，不会错误返回0，但这样判断本身依赖具体数值，不够通用，还是统一用Math.abs(target)更安全。

第二，奇偶判断的先后顺序。两个检查没有严格的先后要求，但逻辑要清楚：如果sum+target是奇数，直接返回0，不用继续往下算capacity。这里还要注意，Java的取模运算符对负数也能正常工作，但sum+target在排除了sum < Math.abs(target)之后不可能为负，所以不需要担心负数取模的边界情况。

第三，capacity等于0的情况。比如target=sum，那么P=sum，意味着所有数字都必须进正号组，只有一种方案。这种case在一维DP里天然成立：如果capacity=0，dp数组长度是1，dp[0]=1，结果直接返回1。很多人会在这里困惑，其实不用特殊处理。

4.3 全零数组的特殊情况

当nums里全是0时，比如nums=[0,0,0,0,0]，target=0，sum=0，capacity=0。按照标准DP写法，dp数组长度是1，外层循环处理每个0，内层循环j>=num，因为num=0，等于每次都会执行dp[0] += dp[0]，执行5次之后，dp[0]从1变成2、4、8、16、32，最终答案是32。

这正确吗？手动验证一下：5个0，每个0前面可以放'+'或'-'，无论怎么放结果都是0，确实有2^5=32种方式。所以算法是对的，dp[0]的翻倍性质恰好模拟了“每个0有两种符号选择”的效果。

这里有个值得注意的点：倒序遍历对num=0没有限制作用，因为j=0时j-num还是0。很多讲背包优化的文章说“一维数组必须倒序”，但遇到num=0时倒序和正序没有区别，甚至这道题恰恰需要它累乘。如果担心混淆，可以在心中把num=0的情况单独理解，并不影响最终代码的正确性。

4.4 记忆化搜索的备选写法

除了DP，还有一个介于回溯和DP之间的方案：记忆化DFS。用HashMap记录(index, currentSum)对应的方案数，避免重复计算。它本质上是把同一棵搜索树的公共子树缓存起来，在某些场景下也能过。代码如下：

import java.util.HashMap; import java.util.Map; class Solution { public int findTargetSumWays(int[] nums, int target) { Map<String, Integer> memo = new HashMap<>(); return dfs(nums, 0, 0, target, memo); } private int dfs(int[] nums, int index, int currentSum, int target, 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, index + 1, currentSum + nums[index], target, memo) + dfs(nums, index + 1, currentSum - nums[index], target, memo); memo.put(key, ways); return ways; } }

这个版本的好处是不用理解复杂的数学转化也能写出来，坏处是记忆化Map在极端场景下内存开销不小，而且currentSum可能是负数，拼Key的时候要注意分隔符。面试时如果时间紧，先写记忆化再引导到DP，也是一种可接受的讲解路径。不过从力扣的提交数据看，DP版本明显更稳定，我还是推荐以DP为主。

5. 同类题型的举一反三与面试讲解顺序

5.1 题型家族：494不是孤立的题

494不是一道孤立题，它属于“子集选择+01背包”这个大家族。刷完这道题，建议顺手把下面几道都过一遍，你会发现它们的骨架惊人地相似：

把这些题放在一起对比，就能明白为什么“背包问题”是面试算法的高频区。它们的模板相似，差异只在容量、价值、数量限制这几个维度上。494恰好是理解“01背包求方案数”的最佳入口，因为它没有额外价值维度，只有一个容量和一个方案数，纯粹得不能再纯粹。

5.2 面试现场的讲题路径

如果你在面试中遇到494，我的建议是分三步讲：

第一步，先给最简单的DFS实现，明确说复杂度O(2^n)，让面试官知道你有枚举能力。第二步，在白板上写出P=(sum+target)/2的推导，解释为什么需要奇偶检查和Math.abs检查。第三步，给出DP递推式，讲清dp[0]=1和倒序遍历的原因，最后能把全零数组的翻倍现象也顺带提一句，绝对加分。

很多候选人死记硬背背包模板，被问到“为什么倒序”就哑火。实际上，倒序是为了避免物品重复使用，能用一句话讲清楚的人，说明是真懂，而不是背模板。面试官真正想考察的，有时候不是你会不会这道题，而是你遇到一道看起来像枚举的题，有没有能力把它抽象成另一个更简单的问题。这个从指数到多项式的跳跃，比代码本身更有说服力。

5.3 我踩过的坑和最后一点体会

我把这道题做过不下五遍，每次隔一段时间再刷，还是会下意识地想用回溯。后来给自己定了一条规矩：凡是看到“每个元素用一次，求方案数”的题目，先停一秒钟，想想能不能转化成容量确定的背包问题。这个思维习惯后来帮我解决了不少看似无关的题。

还有一个小技巧分享给刷题的Java开发者：LeetCode的Java环境默认不需要导包，但如果你在本地IDE里测试记忆化版本，记得import java.util.HashMap和java.util.Map。看起来是小事，我见过不少人在本地跑测试时因为这行import报错卡了好几分钟。另外，代码里的中文注释在本地跑没问题，但LeetCode编辑器有时会因为字符集显示乱码，如果不影响阅读倒也无所谓，介意的话用英文注释就行。

494这道题难度适中，信息量却很足：数学推导、边界判断、背包优化、初始化细节全都有。把它吃透，比盲目刷二十道简单题更有价值。我自己是在把这题从暴力到DP完整演进过一遍之后，才真正理解了背包问题的一维优化，后面再碰到类似题目，基本都能一眼看出套路。