#medium #回溯
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，
nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
提示：
1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
思路
数组 nums 的每个元素都可以添加符号 + 或 -，因此每个元素有 2 种添加符号的方法，n 个数共有 $2^N$ 种添加符号的方法，对应 $2 ^N$ 种不同的表达式。当 n 个元素都添加符号之后，即得到一种表达式，如果表达式的结果等于目标数 target，则该表达式即为符合要求的表达式。
可以使用回溯的方法遍历所有的表达式，回溯过程中维护一个计数器 count，当遇到一种表达式的结果等于目标数 target 时，将 count 的值加 1。遍历完所有的表达式之后，即可得到结果等于目标数 target 的表达式的数目。
int count;
void backtrack(int* nums, int numSize, int target, int index, int sum) {
if (index == numSize) {
if (sum == target)
count++;
} else {
backtrack(nums, numSize, target, index + 1, sum + nums[index]);
backtrack(nums, numSize, target, index + 1, sum - nums[index]);
}
}
int findTargetSumWays(int* nums, int numsSize, int target) {
count = 0;
backtrack(nums, numsSize, target, 0, 0);
return count;
}
记数组的元素和为 sum，添加 - 号的元素之和为 neg，则其余添加 + 的元素之和为 sum−neg，得到的表达式的结果为
$$(sum−neg)−neg=sum−2⋅neg=target$$
即
$$Neg= \frac{Sum−target}{2}$$
由于数组 nums 中的元素都是非负整数，neg 也必须是非负整数，所以上式成立的前提是 sum−target 是非负偶数。若不符合该条件可直接返回 0。
若上式成立，问题转化成在数组 nums 中选取若干元素，使得这些元素之和等于 neg，计算选取元素的方案数。我们可以使用动态规划的方法求解。
定义二维数组 dp，其中 dp[i][j] 表示在数组 nums 的前 i 个数中选取元素，使得这些元素之和等于 j 的方案数。假设数组 nums 的长度为 n，则最终答案为 dp[n][neg]。
当没有任何元素可以选取时，元素和只能是 0，对应的方案数是 1，因此动态规划的边界条件是：
$$
dp[0][j] =
\begin{cases}
1, & \text j = 0 \
0, & \text j \geq 0
\end{cases}
$$
当 $\text 1 \leq i\leq n$ 时，对于数组 nums 中的第 i 个元素 num（i 的计数从 1 开始），遍历 $\text 0 \leq j\leq neg$ \，计算 dp[i][j] 的值：
如果 j<num，则不能选 num，此时有 dp[i][j]=dp[i−1][j]；
如果 j≥num，则如果不选 num，方案数是 dp[i−1][j]，如果选 num，方案数是 dp[i−1][j−num]，此时有 dp[i][j]=dp[i−1][j]+dp[i−1][j−num]。
因此状态转移方程如下：
Dp[i][j]={
Dp[i−1][j],
Dp[i−1][j]+dp[i−1][j−nums[i]],
J<nums[i]
J≥nums[i]
最终得到 dp[n][neg] 的值即为答案。
由此可以得到空间复杂度为 O (n×neg) 的实现。