第一次在力扣上看到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]target3那么有5种组合方式-11111 31-1111 311-111 3111-11 31111-1 3所以答案是5。注意这里每个数字都必须使用不能跳过也就是说每个数字前面必须且只能出现一个符号。这个约束条件决定了它天然是“二选一”的分支结构也就天然适合用DFS去枚举。1.2 最直觉的DFS写法拿到这种“要么A要么B求方案数”的题第一反应自然是深度优先搜索。我从index0开始每到一个位置就尝试一次加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 指数级复杂度的实际感受n15时叶子节点32768完全没问题n20时超过100万勉强能跑n30时约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(sumtarget)/2这个式子要成立必须满足几个前提任何一个不满足就直接返回0第一sumtarget必须是偶数。因为P是整数如果sumtarget是奇数除以2就出现小数说明不存在任何一组正负号分配能凑出target。比如nums[1,2]target1sum3sumtarget4P2可行但如果target2sumtarget5奇数无解。第二sum必须不小于Math.abs(target)。如果数组里所有数字绝对值之和都比目标值小比如nums[1,2]target10sum3无论怎么分配正负号结果最大也就是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]target3。sum5sumtarget8P4。也就是说我需要从5个1里面选出4个1使它们的和等于4。C(5,4)5。这和前面手动枚举出的5种表达式完全对应。再看另一个例子nums[1,2,3]target1。sum6sumtarget7是奇数直接返回0。手动验证一下也能发现无论怎么加正负号得到的结果只可能是6、2、0、-2、-6、-4这些偶数确实不可能等于1。这个验证过程建议自己动手算一遍比单纯背公式更能理解为什么奇偶检查是必要的。3. 动态规划递推与一维数组的倒序玄机3.1 二维DP的状态定义与转移定义dp[i][j]表示只用前i个数字i从0到nums.length能够凑出和恰好为j的方案数。i0时表示一个数字都不用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]为什么等于1dp[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从小到大正序遍历问题就来了。假设num2当j2时更新了dp[2]j4时再去读dp[2]这时dp[2]里已经包含了“用了一次num后的方案数”再把它加一遍等于同一个数字被用了两次。这就不再是01背包而是完全背包即每个物品可以被无限取用。我第一次写这道题的时候就是栽在这里把内层循环写成了正序结果遇到全零数组和适当目标值时答案成倍膨胀怎么都对不上。后来才意识到是物品重复使用的问题。这个坑太经典了值得单独强调一维优化的铁律就是外层循环遍历物品内层循环从capacity到num倒序遍历。3.6 手推一遍递推过程用nums[1,1,1,1,1]target3来演算。sum5P4dp数组长度为5初始化为[1,0,0,0,0]。处理第一个1倒序更新dp[4]dp[4]dp[3]0dp[3]0dp[2]0dp[1]dp[1]dp[0]1得到[1,1,0,0,0]。处理第二个1dp[4]0dp[3]0dp[2]dp[2]dp[1]1dp[1]dp[1]dp[0]2得到[1,2,1,0,0]。处理第三个1dp[4]0dp[3]dp[3]dp[2]1dp[2]134dp[1]213得到[1,3,4,1,0]注意这里dp[2]应该是dp[2]dp[1]即123所以我更正一下正确结果是dp[2]3数组为[1,3,3,1,0]。处理第四个1dp[4]dp[4]dp[3]1dp[3]134dp[2]336dp[1]314得到[1,4,6,4,1]。处理第五个1dp[4]145dp[3]4610dp[2]6410dp[1]415得到[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最大到2000020个数每个最大1000所以性能没有任何压力。提交到LeetCode上运行时间通常在2ms左右属于第一梯队。4.2 常见错误清单这道题的错误集中在几个点上。第一忘记对target取绝对值。有些测试用例的target是负数比如nums[1,2,3]target-6sum6其实答案是1因为-1-2-3-6。如果你用sum target去判断sum6不小于-6不会错误返回0但这样判断本身依赖具体数值不够通用还是统一用Math.abs(target)更安全。第二奇偶判断的先后顺序。两个检查没有严格的先后要求但逻辑要清楚如果sumtarget是奇数直接返回0不用继续往下算capacity。这里还要注意Java的取模运算符对负数也能正常工作但sumtarget在排除了sum Math.abs(target)之后不可能为负所以不需要担心负数取模的边界情况。第三capacity等于0的情况。比如targetsum那么Psum意味着所有数字都必须进正号组只有一种方案。这种case在一维DP里天然成立如果capacity0dp数组长度是1dp[0]1结果直接返回1。很多人会在这里困惑其实不用特殊处理。4.3 全零数组的特殊情况当nums里全是0时比如nums[0,0,0,0,0]target0sum0capacity0。按照标准DP写法dp数组长度是1外层循环处理每个0内层循环jnum因为num0等于每次都会执行dp[0] dp[0]执行5次之后dp[0]从1变成2、4、8、16、32最终答案是32。这正确吗手动验证一下5个0每个0前面可以放或-无论怎么放结果都是0确实有2^532种方式。所以算法是对的dp[0]的翻倍性质恰好模拟了“每个0有两种符号选择”的效果。这里有个值得注意的点倒序遍历对num0没有限制作用因为j0时j-num还是0。很多讲背包优化的文章说“一维数组必须倒序”但遇到num0时倒序和正序没有区别甚至这道题恰恰需要它累乘。如果担心混淆可以在心中把num0的情况单独理解并不影响最终代码的正确性。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) { MapString, Integer memo new HashMap(); return dfs(nums, 0, 0, target, memo); } private int dfs(int[] nums, int index, int currentSum, int target, 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, 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的差异416 分割等和子集sum必须为偶数capacitysum/2布尔dp判断可行性而非方案数1049 最后一块石头的重量II求最接近sum/2的子集和最优值而非方案数473 火柴拼正方形拆成4个容量相等的子集问题需要组合判断常用DFS状态压缩474 一和零二维容量01背包有两个容量维度0的个数和1的个数322 零钱兑换完全背包求最少硬币数硬币可以重复使用518 零钱兑换II完全背包求方案数硬币可以重复使用和494形成正反对比把这些题放在一起对比就能明白为什么“背包问题”是面试算法的高频区。它们的模板相似差异只在容量、价值、数量限制这几个维度上。494恰好是理解“01背包求方案数”的最佳入口因为它没有额外价值维度只有一个容量和一个方案数纯粹得不能再纯粹。5.2 面试现场的讲题路径如果你在面试中遇到494我的建议是分三步讲第一步先给最简单的DFS实现明确说复杂度O(2^n)让面试官知道你有枚举能力。第二步在白板上写出P(sumtarget)/2的推导解释为什么需要奇偶检查和Math.abs检查。第三步给出DP递推式讲清dp[0]1和倒序遍历的原因最后能把全零数组的翻倍现象也顺带提一句绝对加分。很多候选人死记硬背背包模板被问到“为什么倒序”就哑火。实际上倒序是为了避免物品重复使用能用一句话讲清楚的人说明是真懂而不是背模板。面试官真正想考察的有时候不是你会不会这道题而是你遇到一道看起来像枚举的题有没有能力把它抽象成另一个更简单的问题。这个从指数到多项式的跳跃比代码本身更有说服力。5.3 我踩过的坑和最后一点体会我把这道题做过不下五遍每次隔一段时间再刷还是会下意识地想用回溯。后来给自己定了一条规矩凡是看到“每个元素用一次求方案数”的题目先停一秒钟想想能不能转化成容量确定的背包问题。这个思维习惯后来帮我解决了不少看似无关的题。还有一个小技巧分享给刷题的Java开发者LeetCode的Java环境默认不需要导包但如果你在本地IDE里测试记忆化版本记得import java.util.HashMap和java.util.Map。看起来是小事我见过不少人在本地跑测试时因为这行import报错卡了好几分钟。另外代码里的中文注释在本地跑没问题但LeetCode编辑器有时会因为字符集显示乱码如果不影响阅读倒也无所谓介意的话用英文注释就行。494这道题难度适中信息量却很足数学推导、边界判断、背包优化、初始化细节全都有。把它吃透比盲目刷二十道简单题更有价值。我自己是在把这题从暴力到DP完整演进过一遍之后才真正理解了背包问题的一维优化后面再碰到类似题目基本都能一眼看出套路。