Java Solution similar to backpack problem - Easy to understand


  • 44
    T
    public class Solution {
        public boolean canPartition(int[] nums) {
            // check edge case
            if (nums == null || nums.length == 0) {
                return true;
            }
            // preprocess
            int volumn = 0;
            for (int num : nums) {
                volumn += num;
            }
            if (volumn % 2 != 0) {
                return false;
            }
            volumn /= 2;
            // dp def
            boolean[] dp = new boolean[volumn + 1];
            // dp init
            dp[0] = true;
            // dp transition
            for (int i = 1; i <= nums.length; i++) {
                for (int j = volumn; j >= nums[i-1]; j--) {
                    dp[j] = dp[j] || dp[j - nums[i-1]];
                }
            }
            return dp[volumn];
        }
    }
    

  • -9
    C
    This post is deleted!

  • 6
    O

    nice solution ,there is a more concise version

    public boolean canPartition(int[] nums) 
        {
            if(nums == null || nums.length == 0) 
                return true;
            int sum = 0;
            for(int n : nums) sum += n;
            if(sum % 2 != 0 ) return false;
            sum /= 2;
            boolean[] dp = new boolean[sum + 1];
            dp[0] = true;
            // replace nums[i-1] with nums[i]
            for(int i = 0; i < nums.length; ++ i)
            {
                for(int j = sum; j >= nums[i] ; --j)
                    dp[j] = dp[j] || dp[j - nums[i]];
            }
            return dp[sum];
    
    }
    

    ···


  • 3
    L

    @tao62 You are amazing dude!
    Adding the following line in inner for loop helped in improving time.

    if(dp[volumn]==true) return true;

    We eliminate repeated calculations.


  • -1
    P

    The solution is correct, but to correct one point the knapsack solution will use two dimensional array instead of one.
    You should construct your array like this

    dp[nums.length][val]
    

  • 0
    D

    @phhoang Not really. I think the solution here is correct. Can you give any examples that prove it's wrong?


  • 0
    A

    Please explain the working of the solution.


  • 1

  • -1
    H

    This solution fails (gives a runtime error) at the following test case:

    [1,1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296], i.e., a set of 2^i from i=0 to 32 with an extra 1.

    How to fix this?


  • 0
    D

    @tao62
    good solution,but it has a bug,i think.
    1 nums={INT_MAX,INT_MAX,INT_MAX...};or volumn>INT_MAX;
    2 nums={INT_MAX-1,1,1,INT_MAX-1},the space complexity and the time complexity will be very big.


  • 0
    T

    Do you know why we should put loop for i in the outer loop and loop for j in the inner loop? Can we change the position of i and j? I'm just new to dp, really appreciate your help and teach! Thanks!


  • 0

    Can you give some explanation?...
    I cannot understand it.


  • 1
    Z

    For people who are confused about this solution:
    A good explanation:

    https://discuss.leetcode.com/topic/67539/0-1-knapsack-detailed-explanation


  • 15

    Thanks to the author's solution! Very nice!
    Also @ZhuEason Thanks for your solution! Your explanation are quite understandable by intoducing the 2D array way.
    I hope I can make the solution more understandable.
    I think the most tricky part would be:

    for (int i = 1; i <= nums.length; i++) {
        for (int j = volumn; j >= nums[i-1]; j--) {
             dp[j] = dp[j] || dp[j - nums[i-1]];
        }
    }
    

    Since the problem is a 0-1 backpack problem, we only have two choices which are take or not. Thus in this problem, by using the sum value as the index of DP array, we transfer the problem to "whether should we take the currently visited number into the sum or not".
    To construct the DP recurrence, when we are visiting nums[i] and to find partition of sum j: if we do not take the nums[i], then the current iteration does not make any difference on current DP value; if we take the nums[i], then we need to find whether the (new_sum = j - nums[i]) can be constructed. If any of this two construction can work, the partition of sum == j can be reached.

    Hope it helps.


  • 0
    C

    My answer is as follows. Can I ask how you came up with the transition function? Or is it due to an optimization step? Thanks

    bool canPartition(vector<int>& nums) {
    long long sum=0;

       for (auto num : nums){
           sum+=num;
       }
       
       if (sum%2||nums.back()>sum/2)
          return false;
          
       sum/=2;
    
       int num=nums.size();
       vector<vector<bool>> dp(sum+1,vector<bool>(num+1,false));
       dp[0][0]=true;
    
       for (int i=0; i<=sum; i++){
       for (int j=0; j<nums.size(); j++){
              dp[i][j+1]=dp[i][j]||(i>=nums[j]?dp[i-nums[j]][j]:false);
          }
       }
    
       return dp[sum][num];   
    }

  • 0

    Does anyone know why this solution doesn't work? In the question Path Sum iii, we use this method to sum the path to a specific target, and it works fine, but why it doesn't work here :\

    Thanks!

    public boolean canPartition(int[] nums) {
            int sum = 0;
            for (int n : nums) sum += n;
            if ((sum & 1) != 0) return false;
            sum >>>= 1;
            Set<Integer> set = new HashSet();
            set.add(0);
            Arrays.sort(nums);
            int s = 0;
            for (int n : nums) {
                s += n;
                set.add(s);
                if (set.contains(s - sum)) return true;
            }
            return false;
        }
    

  • 4

    nice solution. A couple optimizations you can make to it as follows.

    First, someone else already pointed this one out. You can check for success within your elements loop (outer loop) to possibly terminate early.

    Second, you can start your dp loop (inner loop) from a "max" position which is the lesser of the current sum of all elements used so far or the dp length.

        public bool CanPartition(int[] nums) 
        {
            int sum = 0;
            for (int i = 0; i < nums.Length; i++) sum += nums[i];
            int target = sum / 2;
            if (target * 2 != sum) return false;
            
            bool[] dp = new bool[target + 1];
            dp[0] = true;
    
            int currSum = 0;        
            foreach (int x in nums)
            {
                int max = Math.Min(currSum + x, target);
                for (int j = max; j >= x; j--)
                {
                    dp[j] = dp[j] || dp[j-x];
                }
                
                if (dp[target] == true) return true;
                currSum += x;
            }
            
            return dp[target];
        }
    

  • 0

    Even more concise and of course faster:

    public boolean canPartition(int[] nums) {
            int sum = 0, n = nums.length;
            for (int num : nums) sum += num;
            if ((sum & 1) != 0) return false;
            sum >>>= 1;
            boolean[] dp = new boolean[sum + 1];
            dp[0] = true;
            int curSum = 0;
            for (int x : nums) {
                int max = Math.min(sum, curSum += x);
                for (int j = max; j >= x; j--) {
                    dp[j] = dp[j] || dp[j - x];
                }
                if (dp[sum] == true) return true;
            }
            return dp[sum];
        }
    

  • 0

    @tao62 said in Java Solution similar to backpack problem - Easy to understand:

        // dp transition
        for (int i = 1; i <= nums.length; i++) {
            for (int j = volumn; j >= nums[i-1]; j--) {
                dp[j] = dp[j] || dp[j - nums[i-1]];
            }
        }
    

    Curious why we need 1-based indexing for i. i indicates which element in array nums is being under consideration. Since i's range is [0, n - 1], why not simply -

           for (int i = 0; i < nums.length; i++) {
                 for (int j = volumn; j >= nums[i]; j--) {
                     dp[j] = dp[j] || dp[j - nums[i]];
                 }
           }

  • 0
    V

    @tao62 thanks for your solution. this is good, and perhaps one of the most efficient solutions for this problem. However, I personally prefer ZhuEason's solution posted in the forum. His solution might be less efficient and longer in code... but it is more intuitive. It's very logical and straightforward. Whereas this solution relies on a hidden assumption which actually confused me for some time: The inner loop must proceed in reverse order because otherwise, we will overwrite our dp[j] calculations from the previous iteration of the outer loop. This is just kind of weird and atypical behavior for an algorithm in my opinion. So in my opinion, I will not recommend this approach. I recommend the more intuitive approach in this post:
    https://discuss.leetcode.com/topic/67539/0-1-knapsack-detailed-explanation


Log in to reply
 

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