1 class Solution {
 2     int subset(int []nums, int s)
 3     {
 4         int []dp=new int[s+1];//dp数组代表 从nums找出部分元素求和为s, 有多少种不同的组合?
 5         dp[0]=1; //求和为0当然只有一种办法, 一个元素都不要.
 6         for(int n:nums)
 7             for(int i=s;i>=n;--i)
 8                 dp[i]+=dp[i-n];
 9         return dp[s];
10     }
11     
12     public int findTargetSumWays(int[] nums, int S) {
13         int sum=0;
14         for(int n:nums)
15         {
16             sum+=n;
17         }
18         return (sum<S || (sum+S)%2!=0 ) ? 0: subset(nums,(sum+S)/2);
19     }
20 }

 

参考评论区第一名的答案. 

原题是要求用+ , - 符号来让他们计算和等于某个值, 比较麻烦, 通过 

 2 * sum(P) = target + sum(nums)
变化之后, 问题等价为从数组找一些数字求和为 sumP, 问有多少种办法. 这就可以上dp了. 非常厉害的思路