Java (15 ms) C++ (3 ms) O(ns) iterative DP solution using subset sum with explanation


  • 166
    Y

    The recursive solution is very slow, because its runtime is exponential

    The original problem statement is equivalent to:
    Find a subset of nums that need to be positive, and the rest of them negative, such that the sum is equal to target

    Let P be the positive subset and N be the negative subset
    For example:
    Given nums = [1, 2, 3, 4, 5] and target = 3 then one possible solution is +1-2+3-4+5 = 3
    Here positive subset is P = [1, 3, 5] and negative subset is N = [2, 4]

    Then let's see how this can be converted to a subset sum problem:

                      sum(P) - sum(N) = target
    sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
                           2 * sum(P) = target + sum(nums)
    

    So the original problem has been converted to a subset sum problem as follows:
    Find a subset P of nums such that sum(P) = (target + sum(nums)) / 2

    Note that the above formula has proved that target + sum(nums) must be even
    We can use that fact to quickly identify inputs that do not have a solution (Thanks to @BrunoDeNadaiSarnaglia for the suggestion)
    For detailed explanation on how to solve subset sum problem, you may refer to Partition Equal Subset Sum

    Here is Java solution (15 ms)

        public int findTargetSumWays(int[] nums, int s) {
            int sum = 0;
            for (int n : nums)
                sum += n;
            return sum < s || (s + sum) % 2 > 0 ? 0 : subsetSum(nums, (s + sum) >>> 1); 
        }   
    
        public int subsetSum(int[] nums, int s) {
            int[] dp = new int[s + 1]; 
            dp[0] = 1;
            for (int n : nums)
                for (int i = s; i >= n; i--)
                    dp[i] += dp[i - n]; 
            return dp[s];
        } 
    

    Here is C++ solution (3 ms)

    class Solution {
    public:
        int findTargetSumWays(vector<int>& nums, int s) {
            int sum = accumulate(nums.begin(), nums.end(), 0);
            return sum < s || (s + sum) & 1 ? 0 : subsetSum(nums, (s + sum) >> 1); 
        }   
    
        int subsetSum(vector<int>& nums, int s) {
            int dp[s + 1] = { 0 };
            dp[0] = 1;
            for (int n : nums)
                for (int i = s; i >= n; i--)
                    dp[i] += dp[i - n];
            return dp[s];
        }
    };
    

  • 12
    B

    Awesome idea :) Since it is transformed to a subset problem where the target sum can be compose of a sum of even numbers, we could add a simple if testing S + sum to be even.

         public int findTargetSumWays(int[] nums, int S) {
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
            }
            if(S > sum || (sum + S) % 2 == 1)   return 0;
            return subsetSum(nums, (sum + S) / 2);
        }
    
        private int subsetSum(int[] nums, int S){
            int[] dp = new int[S + 1];
            dp[0] = 1;
            for (int i = 0; i < nums.length; i++) {
                for (int j = S; j >= nums[i]; j--) {
                    dp[j] += dp[j - nums[i]];
                }
            }
            return dp[S];
        }

  • 2
    Y

    @BrunoDeNadaiSarnaglia Thanks for sharing. Your method is even faster (15 ms for Java)
    The helper method names do not match, maybe that's a typo?


  • 0
    B

    @yuxiangmusic My Bad, That was a typo. Just edited it


  • 5
    M

    Thanks for sharing.
    However, I don't quite get the idea. What kind of "subset" problem on which this question is based, another similar question?

    Why do we want to double the value of each cell during the pre-processing?


  • 3
    Y

    @mycoy The subset sum problem is that given nums = [1, 2, 3, 4, 5] we want to find a subset of nums such that its sum is equal to target 9 so in this case [1, 3, 5] is a valid solution.

    I have rephrased the explanation of my original post.


  • 0
    C

    Fantastic Observation.


  • 0
    M

    Hi,

    I just got one question how will your solution work for data
    [-1000000,1000000] 0
    and similar data sets.
    this is likely going to be a segfault


  • 2
    Y

    @marburgcedric The problem statement says "You are given a list of non-negative integers"


  • 0
    M

    yup reading is an important skill :), thanks for pointing this out.
    though even with negative numbers it's doable on a hashmap


  • 0
    A

    I do not agree with this solution. Consider [10, 20] 10000000? Using recursion is instantly fast but your solution is very slow as it will loop from 10 to 10000000. "The length of the given array is positive and will not exceed 20." So recursion solution is more optimal than the dp one


  • 2
    Y

    @adamcai For the example you gave, the DP part will not even be executed because of this line sum < s

    return sum < s || (s + sum) % 2 > 0 ? 0 : subsetSum(nums, (s + sum) >>> 1); 
    

  • 2
    Z

    For people who didn't know subsetSum mean, it is actually a 0-1 knapsack.


  • 7
    K

    explain on the dp part? hope i'm not the only one find it hard to understand.


  • 1
    Y

    @Kenigma The DP part is almost the same problem as Partition Equal Subset Sum It is also a subset sum problem


  • 0
    L

    What a magic!


  • 1

    @yuxiangmusic

    int sum = 0;
    for (int n : nums)
        sum += n;
    

    can be shortened in Java to

    int sum = Arrays.stream(nums).sum();
    

    and

    (s + sum) % 2 > 0
    

    can be changed to use bit magic (like you did later):

    (s + sum) & 1) == 1
    

  • 1
    Y

    @paplorinc

    int sum = Arrays.stream(nums).sum();
    

    will make it significantly slower, that's why I did not use it


  • 0
    M

    @yuxiangmusic
    I think the DP procedure is the same as, 377. Combination Sum IV ?
    But I tried Q337's approach, it doesn't work.
    I'm getting confused between the difference. Could anyone help?

        public int findTargetSumWays(int[] nums, int s) {
            int sum = 0;
            for (int n : nums)
                sum += n;
                
            if( sum < s || (s+sum)%2 == 1 )
                return 0;
            
            //just like 377. Combination Sum IV ??
            int target = (s + sum) / 2; 
            int[] dp = new int[target+1];
            dp[0]=1;
            for(int i=1; i<=target; i++)
                for(int n : nums)
                    if( n<=i )
                        dp[i] += dp[i-n];
            return dp[target]; 
        }
    

  • 2
    Y

    @mycoy 377 allows re-use of an element of nums but subset sum does not


Log in to reply
 

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