LeetCode 第 494 题：目标和（Target Sum） 题目描述 给定一个非负整数数组 nums 和一个目标整数 target ，向数组中的每个整数添加 + 或 - ，使它们的和为 target 。返回可以达成目标的不同表达式数目。 示例： 输入： 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 解题思路 问题转化 将数组分为两个子集：正数子集（和为 P ）和负数子集（和为 N ）。 则需满足： P - N = target ，且 P + N = sum （ sum 为 nums 的总和）。 两式相加得： 2P = target + sum → P = (target + sum) / 2 。 问题转化为： 从 nums 中选取若干数，使它们的和等于 (target + sum) / 2 ，即经典的 0-1 背包问题。 边界条件 若 target + sum 为奇数，则无解（因为 P 必须是整数），返回 0。 若 target 的绝对值大于 sum ，亦无解（无法凑出），返回 0。 动态规划解法 定义状态 设 dp[j] 表示凑出和为 j 的方案数。 初始化 dp[0] = 1 （凑出和为 0 的方案只有不选任何数）。 状态转移 遍历每个数 num ， 倒序 遍历 j 从 P 到 num （避免重复计数）： dp[j] += dp[j - num] 含义：若选取 num ，则方案数继承自 j - num 时的方案数。 示例演算 nums = [1,1,1,1,1] , target = 3 sum = 5 , P = (3+5)/2 = 4 初始化 dp = [1,0,0,0,0] 遍历 num = 1 ： j=4 ： dp[4] += dp[3] → 0 j=3 ： dp[3] += dp[2] → 0 j=2 ： dp[2] += dp[1] → 0 j=1 ： dp[1] += dp[0] → 1 此时 dp = [1,1,0,0,0] 继续遍历剩余 4 个 1 ，最终 dp[4] = 5 。 复杂度分析 时间复杂度： O(n * P) ，其中 n 为数组长度。 空间复杂度： O(P) ，使用滚动数组优化。 关键点 将问题转化为背包问题，避免枚举所有 2^n 种可能。 注意倒序遍历防止同一数字重复使用。