自古圣贤皆寂寞
只教饮者留名
C++，暴力解法和背包。
建议大家暴力解法和背包都能学一下。。。为什么呢？
如果面试的时候，你直接跟面试官开始推出本题中正负数和的公式，那肯定是不讨好面试官的，他会觉得你都没有怎么思考，是背的题。个人建议刷题及面试的时候，应该首先考虑暴力和容易想到的方法。亲身经历，一开始就给出那种很巧妙且复杂度最优的解法，容易被面试官觉得你刷题多，然后故意为难。也就说，面试手撕算法的时候，要体现出你思考的过程，而不是刷题的熟练度。
暴力解法
暴力解法就是dfs了，这道题而言，暴力解法是完全可以的，而且不会超时，因为题目中说了数组长度不会超过20，20个数字的序列，组合方式撑死了\(2^{20}\)种，算下来才\(1024 × 1024\)。。。
也就是说，可以把数组中每个数字前面都用负号和正号，然后进行组合的求和，并判断这个和是否会等于S，然后就标记，最后统计出等于S的组合个数就好了。
具体使用dfs，就是一个前序遍历二叉树的实现，递归地+或-每个元素，到所有元素都遍历完成的时候，最后那个判断target是否等于零。
简单吧！！！！
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
return dfs(nums, S, 0);
}
int dfs(vector<int> &nums, uint target, int left) {
if (target == 0 && left == nums.size()) return 1;
if (left >= nums.size()) return 0;
int ans = 0;
ans += dfs(nums, target - nums[left], left + 1);
ans += dfs(nums, target + nums[left], left + 1);
return ans;
}
};
01背包
本题解参考热评解法
01背包其实不是这种解法的重点，重点是怎么把题目转化成求解01背包的形式。
如果只是单纯的求解和为某个S的组合个数，那就是01背包。。。
但是这题目中不仅有加，还有减，就得进行一个转化了。
思路就是把整个集合看成两个子集，Q表示整个集合，P表示正数子集，N表示负数子集， T表示目标和，用\(S(X)\)表示集合的求和函数，集合中均为非负数，N集合是指选中这部分元素作为负数子集。
\[S(P) - S(N) = T\] \[S(P) + S(N) + S(P) - S(N) = T + S(P) + S(N)\] \[2S(P) = S(Q) + T\]也就是：正数集的和的两倍 == 等于目标和 + 序列总和
所以问题就转换成了，找到一个正数集P，其和的两倍等于目标和+序列总和。。。
简单吧，完全就是01背包了嘛！！！
对于01背包，其实我都差不多背下来了，你会发现背了以后，写着写着，就理解了。
需要注意的是，虽然序列总和不超过1000，但是S可是会接近int的上界。。。很容易出现超过整型范围的操作。
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
long sum = 0;
for (const int &it : nums) sum += it;
if ((S + sum) % 2 == 1 || S > sum) return 0;
S = (S + sum) / 2;
int *dp = new int[S + 1];
memset(dp, 0, (S + 1) * sizeof(int));
dp[0] = 1;
for (const int &it : nums) {
for (int j = S; j >= it; j--)
dp[j] += dp[j - it];
}
int ans = dp[S];
delete[] dp;
return ans;
}
};
