题目给你一个非负整数数组nums和一个整数target。向数组中的每个整数前添加或-然后串联起所有整数可以构造一个表达式例如nums [2, 1]可以在2之前添加在1之前添加-然后串联起来得到表达式2-1。返回可以通过上述方法构造的、运算结果等于target的不同表达式的数目。示例 1输入nums [1,1,1,1,1], target 3输出5解释一共有 5 种方法让最终目标和为 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 1 1 1 1 - 1 3示例 2输入nums [1], target 1输出1提示1 nums.length 200 nums[i] 10000 sum(nums[i]) 1000-1000 target 1000算法定义两个变量数组所有元素总和为S最终表达式里带正号的元素和为 p带负号的元素和为 q。得出下面两个公式所有元素要么带正号、要么带负号所以p q S题目要求表达式结果等于 target即p - q target可以推导出p ( S target) / 2q ( S - target) / 2不管是选 p 还是 q是等价的p 和 q 是互补关系只要你选出一个子集的和等于 p剩下的所有元素自然就组成和为 q 的集合反过来选出一个子集和为 q剩下的自然就是 p。两种选择对应的符号分配方案数完全一一对应最终算出的结果一模一样不存在选谁对、选谁错的区别。为了更快的获取数据所以需要选更小的值外层遍历 n 个元素内层从容量倒序遍历到 0容量越大内层循环的总轮次越多计算开销越高。既然选 p、选 q 结果完全一样那肯定选数值更小的那个当容量让内层循环的范围尽可能小计算效率最高。target 正负两种情况对比 p 和 q 的大小target ≥ 0p (S target)/2q (S - target)/2显然 q p分子里减去了 target结果更小这时候更小的容量是 q (S - target)/2target 0比如 target-3代入公式p (S target)/2 (S - |target|)/2q (S - target)/2 (S |target|)/2显然 p q分子里减去了 | target|结果更小这时候更小的容量是 p (S - |target|)/2所以不管 target 是正还是负两个子集和里更小的那个值永远等于(S - |target|) / 2记忆化每次的计算结果memo[i][c]只使用 nums[0] 到 nums[i] 这些数字凑出总和 c一共有多少种选法。只考虑nums[0..i]这些数字凑出总和恰好为 c 的方案数i 的范围是 0 到 nums.length-1c 的范围是 0 到 (S - |target|) / 2初始化这个数组-1 表示该状态尚未计算用 -1 作为特殊标记。因为方案数量不会是负数所以不会和正常答案冲突。0 表示计算过但确实没有方案上面的思想实现方法有两种DFS递归搜索动态规划后续可以进行空间优化动态规划优化将二维 DP 数组压缩为一维数组减少空间占用同时通过倒序遍历保证每个数字最多使用一次。二维数组状态转移方程为f[i1][c]f[i][c]f[i][c-x]f[i][c]不选当前数字方案数不变f[i][c-x]选择当前数字之前只需要凑出 (c-x)。计算第 (i1) 行时只依赖第 (i) 行并不需要更早的行。使用一维数组实现f[c] f[c-x]f[c]目前已经处理的数字中凑出总和c的方案数。f[c] f[c-x]保留原有方案再加入“选择当前数字”的方案。c必须倒序遍历让f[c-x]保持本轮更新前的值避免重复使用当前数字。含义是处理到当前数字时凑出总和c的方案数。必须倒序遍历每个数字只能使用一次。倒序遍历读取的f[c-x]仍然是处理当前数字之前的旧值确保当前数字最多使用一次。正序遍历读取的f[c-x]可能已经被当前数字更新过导致同一个数字重复使用。这对应完全背包的转移方式。代码递归记忆化搜索importjava.util.Arrays;classSolution{publicintfindTargetSumWays(int[]nums,inttarget){// 1. 计算数组中所有数字的总和ints0;for(intx:nums){sx;}// 2. 将问题转换为子集和问题// s 原本是数组总和// 减去 |target|得到两倍的较小子集之和s-Math.abs(target);// 如果 s 0说明数组总和小于 |target|// 无论如何添加正负号都不可能得到 target//// 如果 s 是奇数那么 s / 2 不是整数// 不存在满足条件的子集if(s0||s%21){return0;}// 3. 转换成统计和恰好等于 m 的子集数量intms/2;// 背包容量即目标子集的和intnnums.length;// memo[i][c] 表示// 只考虑 nums[0..i] 这些数字// 凑出总和恰好为 c 的方案数//// i 的范围是 0 到 n-1// c 的范围是 0 到 mint[][]memonewint[n][m1];// 初始化记忆化数组// -1 表示该状态尚未计算// 0 表示计算过但确实没有方案for(int[]row:memo){Arrays.fill(row,-1);}// 4. 从最后一个数字开始搜索// 统计所有和为 m 的子集数量returndfs(n-1,m,nums,memo);}/** * 统计只使用 nums[0..i] 时 * 凑出总和恰好为 c 的方案数 */privateintdfs(inti,intc,int[]nums,int[][]memo){// 递归终止条件// 所有数字都考虑完了if(i0){// 剩余容量为 0// 一个数字都不选也恰好凑出了目标值// 这种方案有 1 种//// 剩余容量不为 0// 已经没有数字可以选因此方案数为 0returnc0?1:0;}// 如果该状态之前已经计算过直接返回缓存结果if(memo[i][c]!-1){returnmemo[i][c];}// 选择一不选 nums[i]// 目标容量仍然是 c只考虑前面的数字intresdfs(i-1,c,nums,memo);// 选择二选 nums[i]// 只有 nums[i] c 时才能选择// 选择后剩余容量变成 c - nums[i]if(cnums[i]){resdfs(i-1,c-nums[i],nums,memo);}// 缓存当前状态的结果避免重复计算returnmemo[i][c]res;}}动态规划classSolution{publicintfindTargetSumWays(int[]nums,inttarget){ints0;for(intx:nums){sx;}s-Math.abs(target);if(s0||s%21){return0;}intms/2;intnnums.length;int[][]fnewint[n1][m1];f[0][0]1;for(inti0;in;i){for(intc0;cm;c){if(cnums[i]){f[i1][c]f[i][c];// 只能不选}else{f[i1][c]f[i][c]f[i][c-nums[i]];// 不选 选}}}returnf[n][m];}}空间优化1个数组classSolution{publicintfindTargetSumWays(int[]nums,inttarget){// 第一步计算所有数字的总和ints0;for(intx:nums){sx;}// 第二步将目标和问题转换成子集和问题// 转换后的目标子集和为 (sum - |target|) / 2s-Math.abs(target);// 总和不足以达到目标或者无法整除 2都不可能有方案if(s0||s%21){return0;}intms/2;// 背包容量int[]fnewint[m1];// 一个数字都不选凑出总和 0只有一种方案f[0]1;// 依次处理每个数字for(intx:nums){// 倒序遍历避免当前数字被重复使用for(intcm;cx;c--){// 不选 x原有的 f[c] 种方案// 选 x原本凑出 c-x 的方案每种都可以加上 xf[c]f[c-x];}}// 返回凑出目标和 m 的方案数returnf[m];}} 
长河君 · 2026/10/22 2:24:06 · 阅读 1.2k （动态规划+DFS）494. 目标和
题目给你一个非负整数数组nums和一个整数target。向数组中的每个整数前添加或-然后串联起所有整数可以构造一个表达式例如nums [2, 1]可以在2之前添加在1之前添加-然后串联起来得到表达式2-1。返回可以通过上述方法构造的、运算结果等于target的不同表达式的数目。示例 1输入nums [1,1,1,1,1], target 3输出5解释一共有 5 种方法让最终目标和为 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 1 1 1 1 - 1 3示例 2输入nums [1], target 1输出1提示1 nums.length 200 nums[i] 10000 sum(nums[i]) 1000-1000 target 1000算法定义两个变量数组所有元素总和为S最终表达式里带正号的元素和为 p带负号的元素和为 q。得出下面两个公式所有元素要么带正号、要么带负号所以p q S题目要求表达式结果等于 target即p - q target可以推导出p ( S target) / 2q ( S - target) / 2不管是选 p 还是 q是等价的p 和 q 是互补关系只要你选出一个子集的和等于 p剩下的所有元素自然就组成和为 q 的集合反过来选出一个子集和为 q剩下的自然就是 p。两种选择对应的符号分配方案数完全一一对应最终算出的结果一模一样不存在选谁对、选谁错的区别。为了更快的获取数据所以需要选更小的值外层遍历 n 个元素内层从容量倒序遍历到 0容量越大内层循环的总轮次越多计算开销越高。既然选 p、选 q 结果完全一样那肯定选数值更小的那个当容量让内层循环的范围尽可能小计算效率最高。target 正负两种情况对比 p 和 q 的大小target ≥ 0p (S target)/2q (S - target)/2显然 q p分子里减去了 target结果更小这时候更小的容量是 q (S - target)/2target 0比如 target-3代入公式p (S target)/2 (S - |target|)/2q (S - target)/2 (S |target|)/2显然 p q分子里减去了 | target|结果更小这时候更小的容量是 p (S - |target|)/2所以不管 target 是正还是负两个子集和里更小的那个值永远等于(S - |target|) / 2记忆化每次的计算结果memo[i][c]只使用 nums[0] 到 nums[i] 这些数字凑出总和 c一共有多少种选法。只考虑nums[0..i]这些数字凑出总和恰好为 c 的方案数i 的范围是 0 到 nums.length-1c 的范围是 0 到 (S - |target|) / 2初始化这个数组-1 表示该状态尚未计算用 -1 作为特殊标记。因为方案数量不会是负数所以不会和正常答案冲突。0 表示计算过但确实没有方案上面的思想实现方法有两种DFS递归搜索动态规划后续可以进行空间优化动态规划优化将二维 DP 数组压缩为一维数组减少空间占用同时通过倒序遍历保证每个数字最多使用一次。二维数组状态转移方程为f[i1][c]f[i][c]f[i][c-x]f[i][c]不选当前数字方案数不变f[i][c-x]选择当前数字之前只需要凑出 (c-x)。计算第 (i1) 行时只依赖第 (i) 行并不需要更早的行。使用一维数组实现f[c] f[c-x]f[c]目前已经处理的数字中凑出总和c的方案数。f[c] f[c-x]保留原有方案再加入“选择当前数字”的方案。c必须倒序遍历让f[c-x]保持本轮更新前的值避免重复使用当前数字。含义是处理到当前数字时凑出总和c的方案数。必须倒序遍历每个数字只能使用一次。倒序遍历读取的f[c-x]仍然是处理当前数字之前的旧值确保当前数字最多使用一次。正序遍历读取的f[c-x]可能已经被当前数字更新过导致同一个数字重复使用。这对应完全背包的转移方式。代码递归记忆化搜索importjava.util.Arrays;classSolution{publicintfindTargetSumWays(int[]nums,inttarget){// 1. 计算数组中所有数字的总和ints0;for(intx:nums){sx;}// 2. 将问题转换为子集和问题// s 原本是数组总和// 减去 |target|得到两倍的较小子集之和s-Math.abs(target);// 如果 s 0说明数组总和小于 |target|// 无论如何添加正负号都不可能得到 target//// 如果 s 是奇数那么 s / 2 不是整数// 不存在满足条件的子集if(s0||s%21){return0;}// 3. 转换成统计和恰好等于 m 的子集数量intms/2;// 背包容量即目标子集的和intnnums.length;// memo[i][c] 表示// 只考虑 nums[0..i] 这些数字// 凑出总和恰好为 c 的方案数//// i 的范围是 0 到 n-1// c 的范围是 0 到 mint[][]memonewint[n][m1];// 初始化记忆化数组// -1 表示该状态尚未计算// 0 表示计算过但确实没有方案for(int[]row:memo){Arrays.fill(row,-1);}// 4. 从最后一个数字开始搜索// 统计所有和为 m 的子集数量returndfs(n-1,m,nums,memo);}/** * 统计只使用 nums[0..i] 时 * 凑出总和恰好为 c 的方案数 */privateintdfs(inti,intc,int[]nums,int[][]memo){// 递归终止条件// 所有数字都考虑完了if(i0){// 剩余容量为 0// 一个数字都不选也恰好凑出了目标值// 这种方案有 1 种//// 剩余容量不为 0// 已经没有数字可以选因此方案数为 0returnc0?1:0;}// 如果该状态之前已经计算过直接返回缓存结果if(memo[i][c]!-1){returnmemo[i][c];}// 选择一不选 nums[i]// 目标容量仍然是 c只考虑前面的数字intresdfs(i-1,c,nums,memo);// 选择二选 nums[i]// 只有 nums[i] c 时才能选择// 选择后剩余容量变成 c - nums[i]if(cnums[i]){resdfs(i-1,c-nums[i],nums,memo);}// 缓存当前状态的结果避免重复计算returnmemo[i][c]res;}}动态规划classSolution{publicintfindTargetSumWays(int[]nums,inttarget){ints0;for(intx:nums){sx;}s-Math.abs(target);if(s0||s%21){return0;}intms/2;intnnums.length;int[][]fnewint[n1][m1];f[0][0]1;for(inti0;in;i){for(intc0;cm;c){if(cnums[i]){f[i1][c]f[i][c];// 只能不选}else{f[i1][c]f[i][c]f[i][c-nums[i]];// 不选 选}}}returnf[n][m];}}空间优化1个数组classSolution{publicintfindTargetSumWays(int[]nums,inttarget){// 第一步计算所有数字的总和ints0;for(intx:nums){sx;}// 第二步将目标和问题转换成子集和问题// 转换后的目标子集和为 (sum - |target|) / 2s-Math.abs(target);// 总和不足以达到目标或者无法整除 2都不可能有方案if(s0||s%21){return0;}intms/2;// 背包容量int[]fnewint[m1];// 一个数字都不选凑出总和 0只有一种方案f[0]1;// 依次处理每个数字for(intx:nums){// 倒序遍历避免当前数字被重复使用for(intcm;cx;c--){// 不选 x原有的 f[c] 种方案// 选 x原本凑出 c-x 的方案每种都可以加上 xf[c]f[c-x];}}// 返回凑出目标和 m 的方案数returnf[m];}}