LeetCode 494. 目标和 题目描述： 给定一个非负整数数组 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 解题过程循序渐进讲解： 步骤1：问题理解与转化 题目本质是：给定一个数组，你需要为每个数字选择正号（+）或负号（-），使得这些数字的代数和等于 target 。每个数字必须被使用一次。 我们可以将添加 + 的数字归为集合 P（正数部分），添加 - 的数字归为集合 N（负数部分，但我们在表达式中其实是减去它们的绝对值）。那么： 正数部分的和：sum(P) 负数部分的和：-sum(N) 我们希望：sum(P) - sum(N) = target。 设整个数组的总和为 total，即 total = sum(P) + sum(N)。 从上面两个式子，我们可以推导： 从 sum(P) - sum(N) = target 以及 sum(P) + sum(N) = total 两式相加得：2 * sum(P) = target + total 所以 sum(P) = (target + total) / 2 关键转化 ：问题等价于：从数组 nums 中选取若干个数，使得它们的和等于 (target + total) / 2 ，问有多少种不同的选取方法。这变成了一个“子集和”问题（类似背包问题）。 注意前提条件 ： 如果 target + total 是奇数，则无法找到整数 sum(P)，直接返回 0。 如果 target 的绝对值大于 total，则即使全正或全负也达不到，直接返回 0。 步骤2：动态规划定义 定义 dp[j] 表示：填满容量为 j 的背包，有多少种方法。这里的“容量”就是我们需要凑出的正数部分的和，即 pos_sum = (target + total) / 2 。 初始化： dp[0] = 1 ，表示凑出和为 0 的方法有 1 种（什么都不选）。 遍历数组 nums 中的每个数 num ，对于每个数，我们可以选择（放入正数集合）或不选择（不放入正数集合，即放入负数集合）。但注意，在动态规划递推时，为了避免重复计数（每个数字只能用一次），我们需要从后往前更新 dp 数组。 步骤3：动态规划递推 对于每个数字 num ，我们更新 dp 数组，从 j = pos_sum 递减到 num ： dp[j] = dp[j] + dp[j - num] 解释： 左边 dp[j] 表示不选当前数字 num 时，凑出和为 j 的方法数（即上一轮的结果）。 dp[j - num] 表示选了当前数字 num 时，凑出和为 j 的方法数（即上一轮中凑出和为 j - num 的方法数）。 因为每个数字只能用一次，所以从后往前更新，保证在计算 dp[j] 时， dp[j - num] 引用的还是上一轮（即不含当前数字）的结果。 步骤4：举例说明 nums = [ 1,1,1,1,1 ], target = 3 total = 5, target + total = 8, pos_ sum = 4 我们需要从数组中选取若干个数，使它们的和等于 4，求选取方法数。 初始化 dp 数组长度为 pos_ sum+1 = 5： dp = [ 1, 0, 0, 0, 0] // dp[ 0 ]=1 遍历 nums（每个数字都是1）： 第一个1： j 从 4 到 1： j=4: dp[ 4] = dp[ 4] + dp[ 3 ] = 0+0=0 j=3: dp[ 3] = dp[ 3] + dp[ 2 ] = 0+0=0 j=2: dp[ 2] = dp[ 2] + dp[ 1 ] = 0+0=0 j=1: dp[ 1] = dp[ 1] + dp[ 0 ] = 0+1=1 dp变为[ 1,1,0,0,0 ] 第二个1： j=4: dp[ 4] = dp[ 4] + dp[ 3 ] = 0+0=0 j=3: dp[ 3] = dp[ 3] + dp[ 2 ] = 0+0=0 j=2: dp[ 2] = dp[ 2] + dp[ 1 ] = 0+1=1 j=1: dp[ 1] = dp[ 1] + dp[ 0 ] = 1+1=2 dp变为[ 1,2,1,0,0 ] 第三个1： j=4: dp[ 4] = dp[ 4] + dp[ 3 ] = 0+0=0 j=3: dp[ 3] = dp[ 3] + dp[ 2 ] = 0+1=1 j=2: dp[ 2] = dp[ 2] + dp[ 1 ] = 1+2=3 j=1: dp[ 1] = dp[ 1] + dp[ 0 ] = 2+1=3 dp变为[ 1,3,3,1,0 ] 第四个1： j=4: dp[ 4] = dp[ 4] + dp[ 3 ] = 0+1=1 j=3: dp[ 3] = dp[ 3] + dp[ 2 ] = 1+3=4 j=2: dp[ 2] = dp[ 2] + dp[ 1 ] = 3+3=6 j=1: dp[ 1] = dp[ 1] + dp[ 0 ] = 3+1=4 dp变为[ 1,4,6,4,1 ] 第五个1： j=4: dp[ 4] = dp[ 4] + dp[ 3 ] = 1+4=5 j=3: dp[ 3] = dp[ 3] + dp[ 2 ] = 4+6=10 j=2: dp[ 2] = dp[ 2] + dp[ 1 ] = 6+4=10 j=1: dp[ 1] = dp[ 1] + dp[ 0 ] = 4+1=5 dp变为[ 1,5,10,10,5 ] 最终，dp[ 4 ] = 5，即方法数为5，与示例一致。 步骤5：边界与特殊情况 如果 target + total 是奇数，直接返回0。 如果 target 绝对值 > total，直接返回0。 注意，转化后的 pos_sum 必须是非负整数，否则无解。 步骤6：时间复杂度 我们遍历了数组中的 n 个数字，对于每个数字，内层循环从 pos_ sum 递减到该数字的值，因此时间复杂度为 O(n * pos_ sum)。空间复杂度为 O(pos_ sum)。 总结 ： 将原问题转化为“子集和”问题后，使用 0/1 背包的动态规划求解，注意从后往前更新 dp 数组以避免重复使用同一个数字，并处理好边界条件即可得到最终结果。