题目来源
一个数组，每个数字前面选择正号或者负号，问有多少种情况和为S。
实在不会，看了下答案，将其分为正子集和负子集，然后计算出
sum(N) = (target + sum) / 2
并且可以判断出target + sum为偶数。
代码如下：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = accumulate(nums.begin(), nums.end(), 0);
return sum < S || (S + sum) % 2 == 1 ? 0: subsetSum((S+sum)/2, nums);
}
int subsetSum(int s, vector<int> &nums)
{
int n = nums.size();
vector<int> dp(s+1, 0);
dp[0] = 1;
for (int n : nums)
for (int i=s; i>=n; i--)
dp[i] += dp[i-n];
return dp[s];
}
};
