我来给你讲解 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

问题分析

我们需要将数组分成两个子集：

• 正数子集（前面添加 +）
• 负数子集（前面添加 -）

设正数子集的和为 P，负数子集的绝对值和为 N，那么：

1. P - N = target（目标和条件）
2. P + N = sum（所有数的总和）

将两个等式相加：2P = target + sum ⇒ P = (target + sum) / 2

问题转化：从 nums 中选取若干个数，使它们的和等于 (target + sum) / 2，求选取的方案数。

解法思路

方法一：动态规划（0-1背包问题）

状态定义：dp[i][j] 表示用前 i 个数字，组成和为 j 的方案数。

状态转移：

• 不选第 i 个数：dp[i][j] = dp[i-1][j]
• 选第 i 个数：dp[i][j] += dp[i-1][j - nums[i-1]]（如果 j >= nums[i-1]）

初始化：dp[0][0] = 1（用 0 个数组成和为 0 的方案数为 1）

方法二：空间优化的一维DP

由于状态只依赖于上一行，可以优化为一维数组：

• dp[j] 表示组成和为 j 的方案数
• 遍历顺序：外层遍历数字，内层从大到小遍历容量（避免重复计算）

详细解题步骤

步骤1：预处理检查

def findTargetSumWays(nums, target):
    total = sum(nums)
    # 检查是否无解的情况
    if abs(target) > total or (target + total) % 2 != 0:
        return 0
    
    # 计算目标正数和
    pos_sum = (target + total) // 2
    if pos_sum < 0:  # 确保非负
        return 0

步骤2：初始化DP数组

# dp[j] 表示组成和为j的方案数
dp = [0] * (pos_sum + 1)
dp[0] = 1  # 和为0的方案数为1（什么都不选）

步骤3：动态规划计算

for num in nums:
    # 从大到小遍历，避免重复计算
    for j in range(pos_sum, num - 1, -1):
        dp[j] += dp[j - num]

步骤4：返回结果

return dp[pos_sum]

完整代码实现

def findTargetSumWays(nums, target):
    total = sum(nums)
    
    # 边界情况处理
    if abs(target) > total or (target + total) % 2 != 0:
        return 0
    
    pos_sum = (target + total) // 2
    if pos_sum < 0:
        return 0
    
    dp = [0] * (pos_sum + 1)
    dp[0] = 1
    
    for num in nums:
        for j in range(pos_sum, num - 1, -1):
            dp[j] += dp[j - num]
    
    return dp[pos_sum]

示例验证

以 nums = [1,1,1,1,1], target = 3 为例：

1. total = 5
2. pos_sum = (3 + 5) // 2 = 4
3. 问题转化为：从5个1中选出若干个数，使它们的和为4
4. 方案数 = 从5个1中选4个1的组合数 = C(5,4) = 5

运行结果与题目示例一致。

复杂度分析

• 时间复杂度：O(n × pos_sum)，其中 n 是数组长度
• 空间复杂度：O(pos_sum)

关键点总结

1. 问题转化：将加减号分配问题转化为子集和问题
2. 边界处理：检查目标是否可达
3. DP优化：使用一维数组节省空间，注意遍历顺序
4. 初始化：dp[0] = 1 表示空集的方案数

这种方法比暴力搜索的 O(2ⁿ) 高效很多，适用于中等规模的问题。