题面

力扣题目链接-目标和

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5

解释：

-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
一共有5种方法让最终目标和为3。

提示：

  • 数组非空，且长度不会超过 20 。
  • 初始的数组的和不会超过 1000 。
  • 保证返回的最终结果能被 32 位整数存下。

解析

记加负号的元素之和为neg，加正号的元素之和为pos

例如：
给出的数组是 [1，1，1，1，1]
目标的结果是 3
其中的一种组合方法为 +1+1+1 -1 --> pos = 3, neg = 1

$target = pos - ( neg )------①$
这里的关键在于把neg的负号提出来，所以:
$pos + neg = sum(sum是所有元素之和)------②$
②式变换：
$pos = sum - neg------③$
把③带入①式:
$target = (sum - neg) - (neg)------④$
最后：
$neg = \frac{sum - target}{2}$