LeetCode-Go 题解 494. Target Sum加减号符号分配问题的 DP 与 DFS 双解法【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文基于 LeetCode-Go 仓库中 leetcode/0494.Target-Sum/README.md 的官方题解系统讲解 494. Target Sum目标和这道经典中等难度题如何统计给数组每个元素前添加或-符号后总和恰好等于目标值S的方案数。你将掌握两条完整可运行的 Go 解题路径——把问题转化为子集和的动态规划DP做法以及带后缀和剪枝的深度优先搜索DFS做法并看到它们在 494. Target Sum.go 与 494. Target Sum_test.go 中的真实实现与测试验证。题目描述You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbolsand-. For each integer, you should choose one fromand-as its new symbol.Find out how many ways to assign symbols to make sum of integers equal to target S.给定一个非负整数数组nums和一个目标数S数组中的任意一个整数都可以选择在前面添加或-符号。题目要求返回所有添加符号的方式中最终数组和恰好等于目标数S的方法数。示例Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -11111 3 1-1111 3 11-111 3 111-11 3 1111-1 3 There are 5 ways to assign symbols to make the sum of nums be target 3.约束条件数组长度为正数且不会超过 20数组中所有元素的和不会超过 1000保证返回的最终结果能被 32 位整数存下。题目大意给定一个非负整数数组a1, a2, ..., an和一个目标数S对于数组中的任意一个整数从或-中选择一个符号添加在前面返回可以使最终数组和为目标数S的所有添加符号的方法数。解题思路总览原文档明确给出两条思路DP 和 DFS。DFS 方法比较暴力简单DP 做法则需要先完成一次关键的数学转化把符号分配计数问题改写成子集和计数问题。解法一动态规划DP转化为 0-1 背包 / 子集和问题核心数学推导符号分配等价于数组二分题目要求在数组元素前加上或-号其实相当于把数组分成了 2 组一组全部加号记为集合P一组全部加-号记为集合N。设sum(P)、sum(N)分别为两组元素和则可以推出以下关系sum(P) - sum(N) target sum(P) sum(N) sum(P) - sum(N) target sum(P) sum(N) 2 * sum(P) target sum(nums)推导过程即等号两边都加上sum(N) sum(P)于是得到结果2 * sum(P) target sum(nums)。问题降维变成找和为 target 的子集经过上面的推导这道题就转换成了能否在数组中找到这样一个集合其元素和等于(target sum(nums)) / 2。这正是子集和subset sum问题的标准形态因此本题与 LeetCode 416. Partition Equal Subset Sum分割等和子集同源可以直接套用 0-1 背包式的 DP 框架。在 leetcode/0416.Partition-Equal-Subset-Sum/416. Partition Equal Subset Sum.go 中可以看到同构的布尔型背包写法dp[j] dp[j] || dp[j-nums[i]]外层遍历每个数字、内层从容量C向小更新。494 题与 416 题的区别仅在于416 只问是否存在用布尔值494 问有多少种因此dp[i]中存储的是能使和为i的方法个数转移由或变为累加。边界条件直接返回 0 的三种情况如果和不是偶数即(S total) % 2 1或S total 0负数无法作为数组下标与容量或目标S大于数组总和total则说明找不到满足题目要求的解直接输出 0。完整实现对应源码 494. Target Sum.go// 解法一 DP func findTargetSumWays(nums []int, S int) int { total : 0 for _, n : range nums { total n } if Stotal 0 || S total || (Stotal)%2 1 { return 0 } target : (S total) / 2 dp : make([]int, target1) dp[0] 1 for _, n : range nums { for i : target; i n; i-- { dp[i] dp[i-n] } } return dp[target] }关键点逐行解读dp[0] 1和为 0 的方案数为 1即空集这是背包计数的基准状态内层循环倒序遍历for i : target; i n; i--保证每个数字最多被使用一次这是 0-1 背包与完全背包的本质区别——正序会允许同一元素被重复取用转移方程dp[i] dp[i-n]加入当前数字n后和为i的方案数等于不使用n原有的dp[i]加上使用ndp[i-n]的方案数之和空间复杂度由于题目限制sum(nums) 1000target最大仅为 500一维滚动数组即可完成状态压缩后空间为O(target)时间复杂度为O(n * target)相比 DFS 的O(2^n)在数据范围内优势明显。DP 转移的正确性自证以示例nums [1,1,1,1,1], S 3为例验证total 5target (35)/2 4即需要从 5 个 1 中选出若干个 1 使和为 4共有C(5,4) 5种选法对应 5 种符号分配方案与题目输出一致。解法二DFS 深度优先搜索 后缀和剪枝DFS 方法最直观从第一个元素开始每个元素都尝试和-两条分支走到数组末尾时检查当前累加和是否等于S。朴素实现的时间复杂度为O(2^n)在n 20的限制下最坏需搜索约 100 万条路径。源码中的实现通过后缀和剪枝大幅减少无效搜索。完整实现对应源码 494. Target Sum.go// 解法二 DFS func findTargetSumWays1(nums []int, S int) int { // sums[i] 存储的是后缀和 nums[i:]即从 i 到结尾的和 sums : make([]int, len(nums)) sums[len(nums)-1] nums[len(nums)-1] for i : len(nums) - 2; i -1; i-- { sums[i] sums[i1] nums[i] } res : 0 dfsFindTargetSumWays(nums, 0, 0, S, res, sums) return res } func dfsFindTargetSumWays(nums []int, index int, curSum int, S int, res *int, sums []int) { if index len(nums) { if curSum S { *(res) *(res) 1 } return } // 剪枝优化如果 sums[index] 值小于剩下需要正数的值那么右边就算都是 号也无能为力了所以这里可以剪枝了 if S-curSum sums[index] { return } dfsFindTargetSumWays(nums, index1, curSumnums[index], S, res, sums) dfsFindTargetSumWays(nums, index1, curSum-nums[index], S, res, sums) }实现细节拆解后缀和数组sumssums[i]表示nums[i:]从下标i到结尾的所有元素之和。预处理它只需要一次O(n)的后向遍历终止条件index len(nums)时所有元素都已处理完若curSum S则计数res加一剪枝条件S-curSum sums[index]S - curSum是剩余还需要凑出的值sums[index]是剩余元素能提供的最大增量全部取号。如果最大可能的增量都不足以补足差额那么无论剩余元素如何分配符号都无法达到目标直接返回跳过整棵子树结果用指针*int传递res以指针方式传入递归函数保证在递归过程中累加计数可被外部读取。剪枝的直观理解假设当前在index位置累计和为curSum即便把后面所有数字都取号能达到的最大和也只是curSum sums[index]。若这个最大值仍小于目标S即S - curSum sums[index]则从该分支继续深搜永远无解。这一剪枝在数据接近极限时能剪掉大量分支是 DFS 解法能否在时限内跑完的关键。测试验证双解法交叉校验仓库中的测试文件 494. Target Sum_test.go 以表驱动方式构造了两组用例并对两种解法同时做断言输入nums输入S期望输出[1, 1, 1, 1, 1]35[1]20第二个用例直接覆盖了无解分支数组总和total 1 S 2DP 解法在入口处即返回 0DFS 解法枚举完所有符号组合也找不到和为 2 的方案同样返回 0。测试代码对findTargetSumWays与findTargetSumWays1逐一比对输出确保两条不同思路的实现结果完全一致got : findTargetSumWays(p.nums, p.S) if got ! a.one { t.Fatalf(findTargetSumWays(%v, %v) %v, want %v, p.nums, p.S, got, a.one) } if got1 : findTargetSumWays1(p.nums, p.S); got1 ! a.one { t.Fatalf(findTargetSumWays1(%v, %v) %v, want %v, p.nums, p.S, got1, a.one) }本地运行整个 leetcode 包测试即可验证仓库根目录提供了统一脚本 gotest.sh内部执行go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...测试产生的覆盖率汇总在 coverage.txt。单独验证本题可运行go test -v -run Test_Problem494 ./leetcode/0494.Target-Sum/总结与关联题目Target Sum 是符号分配计数类问题的代表其价值在于数学建模通过2 * sum(P) target sum(nums)把看似复杂的2^n枚举问题等价降维成子集和问题这是面试中极具说服力的推导算法迁移降维后的问题与 416. Partition Equal Subset Sum分割等和子集共用同一套 0-1 背包框架416 题是否存在用布尔 DP494 题有多少种用计数 DP两者对照学习可以牢固掌握背包计数模型双解法互相印证DPO(n * target)适合数据规模较大场景DFSO(2^n)最坏、带剪枝适合快速实现与验证正确性仓库内两套实现加交叉测试是学习本题的最佳范本。参考资料LeetCode 原题 494. Target Sum 的完整题解见 leetcode/0494.Target-Sum/README.md对应源码见 494. Target Sum.go测试见 494. Target Sum_test.go。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考