# Short Java DP Solution with Explanation

• ``````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];
}
}
``````

• One more edge case:
if(S<-sum) return 0;

• @notturno Yes. Edited. Thanks!

• 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];
}
};
``````

• One quick question here. Is this solution too I/O intensive?

• @MichaelLeo191 What do you mean? There is no I/O

• @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 non-negative integers, a1, a2, ..., an, and a target, S. "

• Why it can work?

• @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 it

So start with a two dimensional array dp[i][j] which means the number of ways for first i-th element to reach a sum j

we can easily observe that dp[i][j] = dp[i-1][j+nums[i]] + dp[i-1][j-nums[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 i

Another 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 S

Actually most of Sum problems can be treated as knapsack problem, hope it helps

• @cpmvp Thank you,I got it!

• @cpmvp Thank you! It is really helpful!

• Can you tell me why dp[0+sum] = 1 and not 0? since dp[0+sum]is used to store the value of no of combinations with sum 0 which here in the example is 0.

• @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 intuitive

first let's use dp[i][j] represent for first i-th 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

• @Chidong , @cpmvp In the problem here we are supposed to consider all numbers with some sign as a means of choosing. Since 0 cannot be the result of any such combinations it should ideally be zero , right?

• @pbs It is just a base case for future operations.

• @Chidong , @cpmvp I think I got it now. Thanks for the explanation, we are here using a one dimensional array instead of d[i][j] and that is done by just remembering the previous step d[j].

• 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];
}
``````

@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 it

So start with a two dimensional array dp[i][j] which means the number of ways for first i-th element to reach a sum j

we can easily observe that dp[i][j] = dp[i-1][j+nums[i]] + dp[i-1][j-nums[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 i

Another 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 S

Actually most of Sum problems can be treated as knapsack problem, hope it helps

• I have one question, why do we need that "int[] next", why don't simplt have dp[k+nums[i]] += dp[k]?
thanks!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.