Short Java DP Solution with Explanation


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

    0_1485048724190_Screen Shot 2017-01-21 at 8.31.48 PM.jpg


  • 0
    N

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


  • 0

    @notturno Yes. Edited. Thanks!


  • 2
    W

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

  • -4
    M

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


  • 0

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


  • -1
    R

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


  • 1

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


  • 0
    D

    Why it can work?


  • 62

    @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


  • 0
    D

    @cpmvp Thank you,I got it!


  • 0
    X

    @cpmvp Thank you! It is really helpful!


  • 0
    P

    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.


  • 2

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


  • 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


  • 0
    P

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


  • 0

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


  • 0
    P

    @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].


  • 12
    2

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


  • 0
    Y

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


Log in to reply
 

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