public class Solution {
public int findTargetSumWays(int[] nums, int s) {
int sum = 0;
for(int i: nums) sum+=i;
if(s>sum  s<sum) return 0;
int[] dp = new int[2*sum+1];
dp[0+sum] = 1;
for(int i = 0; i<nums.length; i++){
int[] next = new int[2*sum+1];
for(int k = 0; k<2*sum+1; k++){
if(dp[k]!=0){
next[k + nums[i]] += dp[k];
next[k  nums[i]] += dp[k];
}
}
dp = next;
}
return dp[sum+s];
}
}
Short Java DP Solution with Explanation



I have the same idea and used offset with rolling array
this is my C++ code.class Solution { public: int findTargetSumWays(vector<int>& nums, int S) { int dp[2][2005]; int n = nums.size(), sum = 0; memset(dp, 0, sizeof(dp)); dp[1][1000] = 1; for (int i = 0; i < n; i++) { sum += nums[i]; for (int j = nums[i]; j <= 2000  nums[i]; j++) { int tmp = dp[(i % 2) ^ 1][j]; if (tmp) { dp[i % 2][j  nums[i]] += tmp; dp[i % 2][j + nums[i]] += tmp; dp[(i % 2) ^ 1][j] = 0; } } } return S > sum ? 0 : dp[(n  1)% 2][1000 + S]; } };


@chidong Fails for nums = [5, 5] and sum = 10. Is this solution only for positive values in the array?

@ravikanth3 The question says "You are given a list of nonnegative integers, a1, a2, ..., an, and a target, S. "

@demon_sjh
this is a classic knapsack problem
in knapsack, we decide whether we choose this element or not
in this question, we decide whether we add this element or minus itSo start with a two dimensional array dp[i][j] which means the number of ways for first ith element to reach a sum j
we can easily observe that dp[i][j] = dp[i1][j+nums[i]] + dp[i1][jnums[i],
further observation is that each row is only effected by the last row, we can reduce a two dimensional array to two single arrays
dp[i] means the number of ways to reach a sum iAnother part which is quite confusing is return value, here we return dp[sum+S], why is that?
because dp's range starts from sum>0>sum
so we need to add sum first, then the total starts from 0, then we add SActually most of Sum problems can be treated as knapsack problem, hope it helps



@pbs If you use none number from the array, your sum must be 0. You have 1 way to do it. So dp[0+sum] = 1.

@pbs
this base case is not that intuitivefirst let's use dp[i][j] represent for first ith element, whether or not we can reach j weight, then dp[0][0] is true because we can always reach 0 weight even if there is 0 items
since we can always reach 0 weight with 0 items, there must be only one way to do so, so dp[0][0] = 1 in this question


The following is a 2D DP knapsack (with array index translation: from [sum... sum] to [0, 2 * sum] ) solution. It can be converted to 1D DP by rolling arrays or two single arrays easily. Hope it can help understand above 1D DP solution.
public int findTargetSumWays(int[] nums, int S) { if (nums == null) { return 0; } int sum = 0; for (int num : nums) { sum += num; } if (S < sum  S > sum) { return 0;} int n = nums.length; int[][] f = new int[n + 1][2 * sum + 1]; f[0][0 + sum] = 1;//It seems like make no sense, but it is the base value; for (int i = 1; i < n + 1; i++) { //Option 1: easy to understand for (int j = 0; j < 2 * sum + 1; j++) { //f[i][j] = f[i  1][j  nums[i  1]] + f[i  1][j + nums[i  1]]; if (j  nums[i  1] >= 0) { f[i][j] += f[i  1][j  nums[i  1]]; } if (j + nums[i  1] <= 2 * sum) { f[i][j] += f[i  1][j + nums[i  1]]; } } /*//Option 2: efficient but we should think in a reverse way for (int j = nums[i  1]; j < 2 * sum + 1  nums[i  1]; j++) { //for (int j = 0; j < 2 * sum + 1; j++) {//It also works /*if (f[i  1][j] > 0) { //the trick is we should do calculation in a reverse way: //add f[i  1][j] to f[i  1][j +/ nums[i  1]] only when f[i  1][j] != 0 f[i][j  nums[i  1]] += f[i  1][j]; f[i][j + nums[i  1]] += f[i  1][j]; }*/ } return f[n][sum + S]; }
@cpmvp said in Short Java DP Solution with Explanation:
@demon_sjh
this is a classic knapsack problem
in knapsack, we decide whether we choose this element or not
in this question, we decide whether we add this element or minus itSo start with a two dimensional array dp[i][j] which means the number of ways for first ith element to reach a sum j
we can easily observe that dp[i][j] = dp[i1][j+nums[i]] + dp[i1][jnums[i],
further observation is that each row is only effected by the last row, we can reduce a two dimensional array to two single arrays
dp[i] means the number of ways to reach a sum iAnother part which is quite confusing is return value, here we return dp[sum+S], why is that?
because dp's range starts from sum>0>sum
so we need to add sum first, then the total starts from 0, then we add SActually most of Sum problems can be treated as knapsack problem, hope it helps