目标和

难度: Medium

给定一个正整数数组 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 <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

注意：本题与主站 494 题相同： https://leetcode-cn.com/problems/target-sum/

Submission

运行时间: 45 ms

内存: 16.0 MB

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        sum_num = sum(nums)
        if target > sum_num or (target + sum_num) % 2 == 1:
            return 0

        size = (target + sum_num) // 2
        dp = [0 for _ in range(size + 1)]
        dp[0] = 1

        for num in nums:
            for i in range(size, num - 1, -1):
                dp[i] = dp[i] + dp[i - num]

        return dp[size]

Explain

这个题解使用了动态规划的方法解决问题。首先，通过转换问题，我们可以将问题转化为一个子集和问题。原问题是在每个数字前添加'+'或'-'，使得最终的表达式结果等于target。我们可以将这个问题转化为，选择一部分数字使用'+'，另一部分使用'-'，使得这两部分的差等于target。设P为正子集，N为负子集，那么sum(P) - sum(N) = target。同时我们知道sum(P) + sum(N) = sum(nums)，结合这两个等式，我们可以得到sum(P) = (target + sum(nums)) / 2。因此，问题转化为在nums中找到和为(sum(nums) + target) / 2的子集个数。使用动态规划数组dp，dp[i]表示和为i的子集个数。遍历每个数字，更新dp数组。最终dp[size]即为答案。

时间复杂度: O(n*sum)

空间复杂度: O(sum)

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        sum_num = sum(nums)  # 计算数组的总和
        if target > sum_num or (target + sum_num) % 2 == 1:  # 检查是否有解
            return 0

        size = (target + sum_num) // 2  # 转换为子集和问题
        dp = [0 for _ in range(size + 1)]  # 初始化dp数组
        dp[0] = 1  # 和为0的子集有一个，即空集

        for num in nums:  # 遍历每个数字
            for i in range(size, num - 1, -1):  # 更新dp数组
                dp[i] = dp[i] + dp[i - num]  # 通过加上当前数字，更新达到新和的方式数

        return dp[size]  # 返回目标和为size的子集数量

Explore

这个条件是基于数学转换而来的。在原问题中，我们需要找到一种数字的正负标记方式，使得标记后的总和等于目标值 `target`。通过引入两个子集：P为正子集和N为负子集，我们有等式 `sum(P) - sum(N) = target` 和 `sum(P) + sum(N) = sum(nums)`。将这两个等式联立，可以得到 `sum(P) = (sum(nums) + target) / 2`。这个结果 `sum(P)` 必须是一个整数。如果 `sum(nums) + target` 是奇数，那么除以2后得到的结果不是整数，这意味着不存在这样的子集P，使得它们的和为一个非整数值。因此，当 `(sum(nums) + target) % 2 == 1`，即为奇数时，不可能有解。

在动态规划中，`dp[i]` 表示和为i的子集的数量。初始化 `dp[0]` 为1是因为和为0的子集只有一个，即空集。这是基本的边界条件，代表没有选择任何元素时，唯一达到和为0的方法是什么都不选。其他的 `dp[i]` 被初始化为0因为在开始时，没有其他和的子集被发现。这种初始化方式确保了动态规划的正确性，使得后续在更新 `dp` 数组时，每个 `dp[i]` 正确地反映了和为i的子集的数量。

在动态规划中，反向更新 `dp` 数组是为了确保每个数字在每个阶段只被计算一次。如果我们正向更新dp数组，那么在计算 `dp[i]` 时，我们可能会使用同一个 `num` 更新多次，这会导致计算重复，因此会得到错误的结果。反向更新是为了确保当我们处理任何 `dp[i]` 时，依赖的是上一阶段（即还未更新本轮数字前）的 `dp` 数组的值。这样，每个数字对特定和的影响只被计算一次，保证了结果的正确性。