说白了就是让一部分数减去剩下的一部数使得差值为target，计算有多少中组合的方法 下面来个数学公式推导一下
l
e
f
t
+
r
i
g
h
t
=
s
u
m
l
e
f
t
−
r
i
g
h
t
=
t
a
r
g
e
t
l
e
f
t
=
s
u
m
−
l
e
f
t
+
t
a
r
g
e
t
l
e
f
t
=
(
s
u
m
+
t
a
r
g
e
t
)
/
2
left+right = sum\\ left-right=target\\ left=sum-left+target\\ left=(sum+target)/2
left+right=sumleft−right=targetleft=sum−left+targetleft=(sum+target)/2 那么我们现在变成求有多少种方法使得和为left（即我们新的target） 难点就在于我们的递推公式怎么写 dp[j]的含义是在背包容量为j的情况下 有dp[j]种方法使得和为left 假如j为5的话 有一个1的话那么dp[5]有dp[4]种构成 有两个1的话那么dp[5]有dp[3]种构成 有三个1的话那么dp[5]有dp[2]种构成 有四个1的话那么dp[5]有dp[1]种构成 有五个1的话那么dp[5]有dp[5]种构成 因此递推公式就是dp[j] += dp[j-nums[i]]
代码实现
classSolution{public:intfindTargetSumWays(vector<int>& nums,int target){int sum =0;for(int i =0; i < nums.size(); i++){
sum += nums[i];}if(abs(target)> sum){return0;}int our_targrt =(sum + target)/2;if(our_targrt<0||(sum+target)%2==1){// 好好思考一下这两种情况为什么不行return0;}
vector<int>dp(our_targrt+1,0);
dp[0]=1;for(int i =0; i < nums.size(); i++){for(int j = our_targrt; j >= nums[i]; j--){
dp[j]+= dp[j-nums[i]];}}return dp[our_targrt];}};
