目标和：加减号表达式计数

Target Sum

专题: Algorithmic Programming / 算法编程
难度: L4
来源: QuantQuestion

题目详情

给定整数数组 nums 与整数 target。对每个 nums[i] 你可以选择加或减到总和里。

返回能使最终总和等于 target 的不同表达式数量。

You are given an array of integers nums and an integer target.

For each number in the array, you can choose to either add or subtract it to a total sum.

For example, if nums = [1, 2], one possible sum would be "+1-2=-1". If nums=[1,1], there are two different ways to sum the input numbers to get a sum of 0: "+1-1" and "-1+1".

Return the number of different ways that you can build the expression such that the total sum equals target.

Example 1:

Input: nums = [2,2,2], target = 2

Output: 3 Explanation: There are 3 different ways to sum the input numbers to get a sum of 2. +2 +2 -2 = 2 +2 -2 +2 = 2 -2 +2 +2 = 2

Constraints:

1 <= nums.length <= 20 0 <= nums[i] <= 1000 -1000 <= target <= 1000

解析

用 DP 统计“可达和”的方案数：

令 $dp[i]$ 为处理到第 $i$ 个数时，各个可能总和的计数映射。

初始 $dp[0][0]=1$ 。对每个数 $x$ ：

新和 $s+x$ 的计数加上旧计数；
新和 $s-x$ 的计数加上旧计数。

最后返回 $dp[n][target]$ 。

Original Explanation


class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        dp = [defaultdict(int) for _ in range(n + 1)]
        dp[0][0] = 1

        for i in range(n):
            for total, count in dp[i].items():
                dp[i + 1][total + nums[i]] += count
                dp[i + 1][total - nums[i]] += count

        return dp[n][target]