给你一个整数数组 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 <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000 思路
怎么套？
分成两堆， l e f t − r i g h t = t a r g e t left-right=target left−right=target
又因为 l e f t + r i g h t = s u m left+right=sum left+right=sum
所以 l e f t = ( s u m + t a r g e t ) 2 left=cfrac{(sum+target)}{2} left=2(sum+target)
这和以前遇到的题目 不一样
先前：容量为 i 的背包，最多能装多少？
这次：填满容量为 i 的背包，有多少种方法？
五部曲
数组定义
dp[j] 表示：填满容量为 j 的背包，有 dp[j] 种方法
递推公式
分两种情况，一种是不包含当前物品的方法数量，另一种是包含当前物品的方法数量。我们要求的就是二者 之和。为了方便，直接使用一维数组展示：
d
p
[
j
]
=
d
p
[
j
]
+
d
p
[
j
−
n
u
m
s
[
i
]
]
dp[j]=dp[j]+dp[j-nums[i]]
dp[j]=dp[j]+dp[j−nums[i]]
数组初始化
如果是二维数组，也就是要初始化第一行，即只有物品零的情况，可以想见，填满背包容量为零的方法有一种，就是不装东西。但填满不为零的背包的方法却为零，除非物品重量等于背包容量。所以在一维数组中初始化应该是 dp[0]=1 其他为0
遍历顺序
先遍历物品，嵌套遍历背包，且背包遍历要倒序
测试用例
class Solution
{
public:
int findTargetSumWays(vector &nums, int target)
{
int sum = accumulate(nums.begin(), nums.end(), 0);
if ((sum < target) || ((sum + target) % 2) || ((sum + target) < 0))
{
return 0;
}
int left = (sum + target) / 2;
vector dp(left + 1);
dp[0] = 1;
for (int i = 0; i < nums.size(); i++)
{
for (int j = left; j >= nums[i]; j--)
{
dp[j] += dp[j - nums[i]];
}
}
return dp[left];
}
};
