题目链接：https://leetcode-cn.com/problems/target-sum
题目描述：
给你一个整数数组 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 <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
题解：
方法1：回溯法
class Solution {
public:
int ans = 0;
int findTargetSumWays(vector<int>& nums, int target){
int sum = 0;
for(int &iterm : nums)
{
sum += iterm;
}
if(sum < target)
return 0;
trackingBack(nums, target, 0, 0);
return ans;
}
void trackingBack(vector<int>& nums, int target, int index, int sum)
{
if(index == nums.size())
{
if(sum == target)
ans++;
}else{
trackingBack(nums, target, index + 1, sum + nums[index]);
trackingBack(nums, target, index + 1, sum - nums[index]);
}
}
};
方法二：动态规划
设 + 部分数组和为：x， - 部分数字和为：y，可以推出 x + y = target，x - y = sum（nums），合并可得：x = (target + sum（nums）) / 2。
只需计算构成x有几种方案即可，转化为0-1背包问题。
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target){
int sum = 0;
for(int &iterm : nums)
{
sum += iterm;
}
if(sum < target || (sum + target) % 2 != 0)
return 0;
int newTarget = (sum + target) / 2;
vector<int> dp(newTarget + 1, 0); //dp[i]:有dp[i]种方案填满容量为i的背包
dp[0] = 1;
for(int i = 0; i < nums.size(); i++)
{
for(int j = newTarget; j >= nums[i]; j--)
{
dp[j] += dp[j - nums[i]];
}
}
return dp[newTarget];
}
};