1、题目描述：
2、思路：
这道题首先一看，好像可以使用回溯搜索法，把所有的情况找出来，然后相加看是不是为target，若是，则计数器加1。这种思想很朴素，但是，会超时。但是也需要会编写程序啊，我把官方的贴过来吧。是C++代码。
下面是官方给的回溯法的思路：
class Solution {
public:
int count = 0;
int findTargetSumWays(vector<int>& nums, int target) {
backtrack(nums, target, 0, 0);
return count;
}
void backtrack(vector<int>& nums, int target, int index, int sum) {
if (index == nums.size()) { // 到达边界，说明一次遍历完了
if (sum == target) { // 符合条件
count++; // 计数器加一
}
} else {
backtrack(nums, target, index + 1, sum + nums[index]); // 第一种情况：前面添加+
backtrack(nums, target, index + 1, sum - nums[index]); // 第二种情况：前面添加-
}
}
};
下面，看看动态规划的思路。需要转化问题。
原问题等同于： 找到nums一个正子集P和一个负子集N，使得总和等于target。即sum(P) - sum(N) == target，
即sum(P) + sum(N) + sum(P) - sum(N) == sum(P) + sum(N) + target
即2 * sum(P) == target + sum(nums)， 其中target + sum(nums)必须>=0且为偶数，否则等式不可能成立。
则问题转换为：存在多少个子集P，使sum(P) == (target + sum(nums))/2。
（到达这一步的时候，发现就是找组合啊，所以这里还可以使用回溯法求组合，代码在下面）
那动态规划是怎么做的呢？
dp[i][j]表示从0-i的数中取数，放到和为j的背包中，刚好能填满j的总共的取法有多少种。
(1)当dp[i][j] > j时，i这个数放不下，则dp[i][j] = dp[i-1[j];
(2)当dp[i][j] <= j时，i这个数能放下，则如果不选i，方案数是dp[i?1][j]，
如果选 i，方案数是dp[i?1][j?num[i]]，此时总共的方案是就是两种情况的和，即：
dp[i][j]=dp[i?1][j] + dp[i?1][j?num]。
最终得到的dp[len(nums)][P]就是结果。
那么dp怎么初始化呢？
答：当只有0个数，总和为0时，有一种方法，那就是不取。所以dp[0][0]=1;
当取第一个数时，第一个数等于背包容量j有一种方法，即，dp[0][j]=1，其他可能都为0。
这里面还有一个特殊的情况，那就是：背包容量为0，当第一个数为0时，不取和取都可以，所以dp[0][0]=2
3、代码：
3.1 python代码（回溯法）：
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
if (target + sum(nums)) % 2 != 0: # 如果不符合这个条件，那么不可能有目标和
return 0
count = 0 # 记录符合条件的个数
left = (target + sum(nums)) // 2 # 从nums中寻找组合，是的和为left
def backtrack(startIndex, s):
nonlocal count
if s == left: # 和为left，则计数加1
count += 1
for i in range(startIndex, len(nums)):
s += nums[i] # 求和（处理节点）
if s > left: # 剪枝，这个break需要排序才能剪枝
break
backtrack(i+1, s) # 递归
s -= nums[i] # 回溯
nums.sort() # 排序才能剪枝
backtrack(0, 0)
return count
上面的代码超时了。。。。。。
下面看看动态规划怎么解决的。
3.2 python代码：
"""
原问题等同于： 找到nums一个正子集P和一个负子集N，使得总和等于target。即sum(P) - sum(N) == target，
即sum(P) + sum(N) + sum(P) - sum(N) == sum(P) + sum(N) + target
即2 * sum(P) == target + sum(nums)， 其中target + sum(nums)必须>=0且为偶数，否则等式不可能成立。
则问题转换为：存在多少个子集P，使sum(P) == (target + sum(nums))/2。
（到达这一步的时候，发现就是找组合啊，所以这里还可以使用回溯法求组合，代码在下面）
那动态规划是怎么做的呢？
dp[i][j]表示从0-i的数中取数，放到和为j的背包中，刚好能填满j的总共的取法有多少种。
(1)当dp[i][j] > j时，i这个数放不下，则dp[i][j] = dp[i-1[j];
(2)当dp[i][j] <= j时，i这个数能放下，则如果不选i，方案数是dp[i?1][j]，
如果选 i，方案数是dp[i?1][j?num[i]]，此时总共的方案是就是两种情况的和，即：
dp[i][j]=dp[i?1][j] + dp[i?1][j?num]。
最终得到的dp[len(nums)][P]就是结果。
那么dp怎么初始化呢？
答：当只有0个数，总和为0时，有一种方法，那就是不取。所以dp[0][0]=1;
当取第一个数时，第一个数等于背包容量j有一种方法，即，dp[0][j]=1，其他可能都为0。
这里面还有一个特殊的情况，那就是：背包容量为0，当第一个数为0时，不取和取都可以，所以dp[0][0]=2
"""
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
if (target + sum(nums)) % 2 != 0 or (target + sum(nums)) < 0: # 小于0或者非偶数
return 0
P = (target + sum(nums)) // 2 # 背包容量
dp = [[0 for _ in range(P+1)] for _ in range(len(nums))] # dp数组初始化0
# 初始化dp边界
for j in range(P+1):
if j == nums[0] or j == 0: # 第一个数等于背包容量j 或者 背包容量为0，则各有一种方法，其他可能都为0
dp[0][j] = 1
if nums[0] == 0: # 这个是因为：背包容量为0，当第一个数为0时，不取和取都可以，所以为2
dp[0][0] = 2
for i in range(1, len(nums)): # 遍历物品,i表示物品。从1开始是因为:第一个数已经初始化了
for j in range(P+1): # 遍历背包,j表示背包容量
if j < nums[i]: # 装不下i
dp[i][j] = dp[i-1][j] # 那就不装i了,依然还是i-1的状态
else: # 能装下i时
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]] # 那就有不装i和装i两种方法
print(dp)
return dp[-1][-1]
3.3 C++代码：
/*
原问题等同于： 找到nums一个正子集P和一个负子集N，使得总和等于target。即sum(P) - sum(N) == target，
即sum(P) + sum(N) + sum(P) - sum(N) == sum(P) + sum(N) + target
即2 * sum(P) == target + sum(nums)， 其中target + sum(nums)必须>=0且为偶数，否则等式不可能成立。
则问题转换为：存在多少个子集P，使sum(P) == (target + sum(nums))/2。
（到达这一步的时候，发现就是找组合啊，所以这里还可以使用回溯法求组合，代码在下面）
那动态规划是怎么做的呢？
dp[i][j]表示从0-i的数中取数，放到和为j的背包中，刚好能填满j的总共的取法有多少种。
(1)当dp[i][j] > j时，i这个数放不下，则dp[i][j] = dp[i-1[j];
(2)当dp[i][j] <= j时，i这个数能放下，则如果不选i，方案数是dp[i?1][j]，
如果选 i，方案数是dp[i?1][j?num[i]]，此时总共的方案是就是两种情况的和，即：
dp[i][j]=dp[i?1][j] + dp[i?1][j?num]。
最终得到的dp[len(nums)][P]就是结果。
那么dp怎么初始化呢？
答：当只有0个数，总和为0时，有一种方法，那就是不取。所以dp[0][0]=1;
当取第一个数时，第一个数等于背包容量j有一种方法，即，dp[0][j]=1，其他可能都为0。
这里面还有一个特殊的情况，那就是：背包容量为0，当第一个数为0时，不取和取都可以，所以dp[0][0]=2
*/
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = accumulate(nums.begin(), nums.end(), 0); // 求和
if((target + sum) % 2 != 0 || (target + sum) < 0){
return 0;
}
int P = (target + sum) / 2; // 背包容量
vector<vector<int>> dp(nums.size(), vector(P+1, 0)); // 定义dp数组，并初始化为0
// 初始化dp边界
dp[0][0] = 1; // 背包容量和物品都为0，则有一种取法
if(nums[0] <= P){
dp[0][nums[0]] = 1; // 背包容量为nums[0]，取第一个物品，则有一种取法（刚好放下）
}
if(nums[0] == 0){ // 背包容量为0，当第一个数为0时，不取和取都可以，所以dp[0][0]=2
dp[0][0] = 2;
}
for(int i = 1; i < nums.size(); i++){ // 遍历物品
for(int j = 0; j <= P; j++){ // 遍历背包
if(j < nums[i]){ //i物品装不下j背包
dp[i][j] = dp[i-1][j];
}
else{ // i物品能装下，则有装和不装两种选择
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]];
}
}
}
return dp[nums.size()-1][P];
}
};
4、总结：
这道题把我整的半死，下次遇到类似的怕还是做不出来。总结一下这道题吧，这道题的关键在于分成正负两部分来考虑，因此，只需要找子集和=正半部分即可（找左半部分也可以）。
关于怎么找子集和等于目标值，一般可以使用回溯法（找组合的模板求解），如果像本题使用动态规划，那么就要用0-1背包的思想做，把数字看作物品，把正半部分的那个值看作价值，dp[i][j]表示：从0-i物品中随便选择数字，使得和为j，的选法。