Target Sum
给你一个由非负整数构成的数组 nums 和一个整数 target。在每个数字前面放一个加号或减号，保持它们的顺序，然后计算表达式。返回能使表达式等于 target 的符号选择有多少种。2^n 种选择都分别计数，因此 +0 和 -0 是两种不同的选择。
函数
- numsinteger-array
- 这些数字，每个都会带有一个符号
- targetinteger
- 表达式必须等于的值
- 返回值integer
- 表达式等于目标值的符号选择数量
约束条件
1 ≤ nums.length ≤ 200 ≤ nums[i] ≤ 1000nums的总和最多为 1000。-1000 ≤ target ≤ 1000- 答案最多为 220，远小于 32 位有符号整数的范围。
示例
- 输入
- nums = [2, 1, 1]target = 2
- 输出
- 2
- 解释
+2 +1 -1和+2 -1 +1都等于 2。给 2 加上负号后，你最多只能得到 -2 + 1 + 1 = 0，所以其他选择都不行。
- 输入
- nums = [0, 4, 4]target = 0
- 输出
- 4
- 解释
- 两个 4 需要使用相反的符号，即
+4 -4或-4 +4，这两种情况下，0 都可以使用任一符号。因此共有 2 × 2 = 4 种选择。
- 输入
- nums = [6, 3]target = 4
- 输出
- 0
- 解释
- 四种可能的值是 9、3、-3 和 -9。翻转符号会让总和改变该数字的两倍，因此每个结果都是奇数，例如 6 + 3 = 9，而且永远无法得到偶数目标值 4。
进阶
当总和索引的数组无法放入内存时，你能处理最多 40 个数，且每个数的值最大为 10^9 吗？
提示
逐个打开提示，每个都会多透露一点。
你可以为每个数字尝试两种符号，这样会有
2^n个表达式。注意，许多不同的符号前缀会得到相同的累计总和，从那之后，它们的行为就完全相同了。把得到加号的数字之和称为
P，把得到减号的数字之和称为N。你知道P - N = target且P + N = sum(nums)。这能告诉你关于P的什么信息？P = (sum + target) / 2，因此要统计总和等于该值的nums子集。保留ways[s]，表示总和达到s的子集数量，并对每个数字从最大的s开始向下更新。如果sum + target是奇数，或|target| > sum，则立即返回 0。
题解
每个数字都有两种符号，因此共有 2^n 个表达式。按位置和当前总和进行计数，可以合并得到相同总和的符号前缀。更进一步，带加号的数字构成一个和固定的子集，因此这个问题就转化为统计和为指定值的子集，时间复杂度为 O(n × S)，其中 S 是 nums 的总和。
为每个数字都试试这两种符号
结果正确，但无法在最大的测试中运行完毕
思路
从左到右遍历这些数字，并记录累计总和。对每个数字分成两种情况：加上它，或减去它。给每个数字都加上符号后，如果总和等于 target，就计数 1。每次符号选择都对应一条路径，因此计数之和就是答案。
每种选择对应一片叶子：20 个数字会有 2^20 ≈ 10^6 片叶子，每增加一个数字，工作量就会翻倍。
算法
- 编写
count(i, total)，计算前面的数字之和已为total时，给nums[i..]中的数字添加符号的方法数。 - 如果
i == n，当total == target时返回 1，否则返回 0。 - 否则返回
count(i+1, total + nums[i]) + count(i+1, total - nums[i])。 - 答案是
count(0, 0)。
def findTargetSumWays(nums, target):
n = len(nums)
def count(i, total):
# Ways to sign nums[i:] so that the whole expression ends at target
if i == n:
return 1 if total == target else 0
return count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])
return count(0, 0)按位置和当前总和进行记忆化
思路
count(i, total) 只取决于 i 和 total，而不取决于得到总和的符号。对于 nums = [1, 1, 1, 1]，前缀 +1 -1 和 -1 +1 都会在位置 2 得到总和 0，所以从那里开始的搜索是相同的。首次计算每个结果时将其存储起来，然后重复使用。
运行中的总和始终处于 -S 和 S 之间，因此将其加上 S，作为索引使用：memo[i][total + S]。状态最多有 n × (2S+1) 个，对于总和为 1000 的 20 个数字，大约有 4 × 10^4 个状态，每个状态只需常数级的工作量。
算法
- 计算
S = sum(nums)，并创建一个填满 -1 的n × (2S+1)备忘录。 - 在
count(i, total)中，像之前一样，在i == n时返回基本情况。 - 如果
memo[i][total + S]是 -1，就将其填为count(i+1, total + nums[i]) + count(i+1, total - nums[i])。 - 返回存储的值，并调用
count(0, 0)。
def findTargetSumWays(nums, target):
n = len(nums)
whole = sum(nums)
# memo[i][total + whole]: ways for nums[i:] from this running total, -1 while unknown
memo = [[-1] * (2 * whole + 1) for _ in range(n)]
def count(i, total):
if i == n:
return 1 if total == target else 0
if memo[i][total + whole] == -1:
memo[i][total + whole] = count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])
return memo[i][total + whole]
return count(0, 0)统计总和为 (S + target) / 2 的子集数量
思路
令 P 为带加号的数字之和，令 N 为其余数字之和。那么 P - N = target 且 P + N = S，所以 2P = S + target。当且仅当加号组的和为 (S + target) / 2 时，这种符号选择才有效，并且每个这样的子集都对应一种符号选择。
ways[s] 统计到目前为止看到的数字中，和为 s 的子集数量，初始值为 ways[0] = 1。对于每个数字 x，和为 s 的子集要么不选 x，要么将它加入一个和为 s - x 的子集。从最大的 s 开始递减遍历，这样 ways[s - x] 仍保留加入 x 之前的值，每个数字就不会被重复使用。遇到 0 时，每个条目都会加到自身上，使所有计数翻倍：这对应 0 的两种符号。总共需要 n × goal 次加法，最多为 2 × 10^4。
算法
- 计算
S = sum(nums)。如果|target| > S，或者S + target是奇数，则返回 0。 - 设置
goal = (S + target) / 2，创建一个包含goal + 1个零的ways，并设置ways[0] = 1。 - 对于
nums中的每个x，让s从goal递减到x，将ways[s - x]加到ways[s]上。 - 返回
ways[goal]。
def findTargetSumWays(nums, target):
whole = sum(nums)
# plus - minus = target and plus + minus = whole, so plus = (whole + target) / 2
if abs(target) > whole or (whole + target) % 2 == 1:
return 0
goal = (whole + target) // 2
# ways[s]: how many subsets of the values seen so far add up to s
ways = [0] * (goal + 1)
ways[0] = 1
for x in nums:
# From the top down, so each value is used at most once
for s in range(goal, x - 1, -1):
ways[s] += ways[s - x]
return ways[goal]
易错点和边界情况
- 跳过奇偶性检查。对于
[6, 3]和目标值 4，(9 + 4) / 2向下取整为 6，而子集{6}得到的是 1，而不是 0。 - 跳过范围检查。对于
[1, 2, 3]和目标值 -10，(6 - 10) / 2 = -2，数组大小为负数。 - 从底向上填充
ways。这样，数字会加入一个已经使用过它的子集：对于目标值为 2 的[1, 3]，结果是 2，而不是 1。 - 把 0 当作一种选择。对于目标值为 -1 的
[0, 0, 0, 1, 0, 0]，有 32 种答案，每种对应五个 0 的一种符号组合。 - 用负的当前总和作为备忘录的索引。将每个总和都加上
S进行偏移，或使用哈希映射。
常见问题3
Target Sum 与子集和问题有什么关系？
带加号的数字之和必须等于 (S + target) / 2，所以答案是 nums 中和为该值的子集数量。只要再加上两个检查，任何统计子集和的动态规划都能解决这个问题：该值必须是整数，并且 |target| 不能大于 S。
Target Sum 的时间复杂度是多少？
子集计数 DP 的时间复杂度为 O(n × S)，空间复杂度为 O(S)，其中 S 是 nums 的总和。记忆化递归的时间复杂度相同，但需要一个大小为 n × (2S+1) 的表。尝试每种符号的时间复杂度为 O(2^n)。
可以用记录累计总和的哈希表来解决 Target Sum 吗？
是的。把每个可达的运行总和映射到达到该总和的正负号前缀数量，初始值为 {0: 1}，然后对每个数字，通过 total + x 和 total - x 构建下一张映射。答案就是 target 对应的数量。这相当于向前运行记忆化递归，时间复杂度同样是 O(n × S)。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def findTargetSumWays(nums, target):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [2, 1, 1] target = 2
预期输出
2