LeetCode 494：目标和（Target Sum）—— 题解 ✅

LeetCode 494目标和Target Sum—— 题解 ✅ 题目链接 https://leetcode.cn/problems/target-sum/ 内容概要给定一个非负整数数组nums和一个整数target你可以在每个数字前加或-使计算结果等于target。返回所有可能的表达式数量。✅ 0/1 背包计数问题✅ 数学转化是关键✅ 面试高频题 解题思路核心一、关键数学转化非常重要设正数和为P负数绝对值和为N则有P - N target P N sum解得P (sum target) / 2问题转化为从数组中选出若干数使其和正好等于P二、不可行的情况剪枝情况原因(sum target)为奇数无法整除targetif((sumtarget)%21)return0;if(Math.abs(target)sum)return0;三、DP 定义dp[j]和为 j 的方案数四、状态转移方程dp[j]dp[j-nums[i]];✅ 每个数只能用一次✅ 倒序遍历0/1 背包五、初始化dp[0]1;什么都不选是一种方案✅ AC 代码JavaclassSolution{publicintfindTargetSumWays(int[]nums,inttarget){intsum0;for(inta:nums){suma;}intleft(sumtarget)/2;// 剪枝if((sumtarget)%21)return0;if(Math.abs(target)sum)return0;int[]dpnewint[left1];dp[0]1;// 0/1 背包计数for(inti0;inums.length;i){for(intjleft;jnums[i];j--){dp[j]dp[j-nums[i]];}}returndp[left];}}⏱️ 复杂度分析指标复杂度时间复杂度O(n × sum)空间复杂度O(sum) 与 416 / 1049 的对比题目目标416. 分割等和子集是否存在1049. 最后一块石头 II最小差值494. 目标和方案数✅ 三题本质都是子集和问题✅ 区别在于 DP 含义不同✅ 一句话总结把“加减符号问题”转化为“子集和为 P 的方案数问题”再用 0/1 背包计数。 面试加分点建议记住✅ 为什么是(sum target) / 2✅ 为什么dp[0] 1✅ 为什么是而不是max✅ 与回溯法的对比会超时