目标和

难度: 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

Submission

运行时间: 41 ms

内存: 16.1 MB

# class Solution:
    # def findTargetSumWays(self, nums: List[int], target: int) -> int:
    #     # target = abs(target)
    #     sum_nums = sum(nums)
    #     tmp = sum_nums + target
    #     if tmp % 2:
    #         return 0

    #     n = tmp // 2
    #     m = len(nums)
    #     dp = [0] * (n+1)
    #     dp[0] = 1

    #     for i in range(m):
    #         for j in range(n, -1, -1):
    #             if j >= nums[i]:
    #                 dp[j] = dp[j] + dp[j-nums[i]]
        
    #     return dp[-1]

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total_sum = sum(nums)  # 计算nums的总和
        if abs(target) > total_sum:
            return 0  # 此时没有方案
        if (target + total_sum) % 2 == 1:
            return 0  # 此时没有方案
        target_sum = (target + total_sum) // 2  # 目标和
        dp = [0] * (target_sum + 1)  # 创建动态规划数组，初始化为0
        dp[0] = 1  # 当目标和为0时，只有一种方案，即什么都不选
        for num in nums:
            for j in range(target_sum, num - 1, -1):
                dp[j] += dp[j - num]  # 状态转移方程，累加不同选择方式的数量
        return dp[target_sum]  # 返回达到目标和的方案数


    # def findTargetSumWays(self, nums: List[int], target: int) -> int:
    #     target = abs(target)
    #     if len(nums) == 1 and nums[0] == target:
    #         return 1

    #     dp = []
    #     m = len(nums)
    #     n = sum(nums)
    #     if n < target:
    #         return 0
        
    #     for i in range(m):
    #         tmp = [0]*(n+1)
    #         dp.append(tmp[:])
        
    #     for i in range(m):
    #         for j in range(n+1):
    #             if not i and j == nums[i]:
    #                 if j == 0:
    #                     dp[i][j] = 2
    #                 else:
    #                     dp[i][j] = 1
    #                 continue
                
    #             if abs(j-nums[i]) <= n:
    #                 left = dp[i-1][abs(j-nums[i])]
    #             else:
    #                 left = 0

    #             if j+nums[i] <= n:
    #                 right = dp[i-1][j+nums[i]]
    #             else:
    #                 right = 0

    #             dp[i][j] = left + right
    #         # print(dp)
        
    #     return dp[-1][target]

Explain

这个题解使用动态规划的思路来解决目标和问题。首先计算数组nums的总和total_sum，如果目标值target的绝对值大于总和或者(target + total_sum)不能被2整除，则无解返回0。否则，将问题转化为在nums中选择一些数，使得它们的和等于(target + total_sum) / 2。创建一个动态规划数组dp，其中dp[i]表示选择nums中的数，使得它们的和等于i的方案数。初始化dp[0]=1，表示当目标和为0时，只有一种方案，即什么都不选。然后遍历nums中的每个数num，对于每个可能的和j，更新dp[j] += dp[j-num]，表示在之前的方案数的基础上，加上选择当前数num得到和为j的方案数。最终返回dp[target_sum]，即达到目标和的方案总数。

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

空间复杂度: O(target_sum)

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total_sum = sum(nums)  # 计算nums的总和
        if abs(target) > total_sum:
            return 0  # 此时没有方案
        if (target + total_sum) % 2 == 1:
            return 0  # 此时没有方案
        target_sum = (target + total_sum) // 2  # 目标和
        dp = [0] * (target_sum + 1)  # 创建动态规划数组，初始化为0
        dp[0] = 1  # 当目标和为0时，只有一种方案，即什么都不选
        for num in nums:  # 遍历nums中的每个数
            for j in range(target_sum, num - 1, -1):  # 遍历目标和的可能取值
                dp[j] += dp[j - num]  # 状态转移方程，累加不同选择方式的数量
        return dp[target_sum]  # 返回达到目标和的方案数

Explore

这个条件基于将原问题转化为一个子集和问题的数学推导。原问题要求通过添加正负号使得数组nums的元素之和等于target。将所有添加了正号的元素和记为P，负号的元素和记为N，那么P - N = target。同时又有P + N = total_sum。联立这两个方程，解得P = (target + total_sum) / 2。由于P是一组元素的和，必须是非负整数。因此，如果target + total_sum是奇数，那么P无法为整数，从而无解。

在这个动态规划问题中，dp[i]代表从数组nums中选取若干个元素，其和为i的方案数。初始化dp[0]=1是因为和为0的方案数恰好有一种，即不选择任何元素。这个初始化是方案计数的基础，使得在后续的动态规划计算中，每次考虑添加新元素到已有子集中时，都可以正确计数。

在更新dp数组时，如果从0开始向上遍历到target_sum，那么在计算dp[j]时，dp[j-num]可能已经被更新过，这将导致重复计算某些方案。例如，如果num可以被多次累加计入同一个dp[j]中，就会错误地统计多种方案。而从target_sum向下遍历到num-1可以确保在更新dp[j]时，dp[j-num]尚未被本轮循环更新，从而避免了重复计算，确保每个元素在每个目标和中只被计算一次。

当nums中包含0时，需要特殊处理，因为选择0的次数可以是任意多次（包括0次）。这种情况下，对于任何已经存在的方案数dp[i]，选择0的方案可以增加新的组合方式。具体来说，你可以将每个dp[i]乘以2的零的个数次方（因为每个0都可以选择或不选择），从而正确计算出包含0的情况下，达到每个i的方案数。这一点需要在动态规划迭代过程中额外考虑。