Java backpack solution


  • 0
    Z

    This question can convert to 0 1 backpack question, the target is sum/k.

    public boolean canPartitionKSubsets(int[] nums, int k) {
            if (nums == null || nums.length == 0) {
                return false;
            }
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            if (sum % k != 0) {
                return false;
            }
            int target = sum / k;
            int[] dp = new int[target + 1];
            dp[0] = 1;
            for (int num : nums) {
                for (int i = target; i >= num; i--) {
                    dp[i] += dp[i - num];
                }
            }
            return dp[target] >= k;
        }
    

  • 0
    L

    Brillant solution!

    Could you explain why the final judging requirement is

    return dp[target] >= k;
    

    instead of

    return dp[target] == k;
    

    Thanks.


  • 5
    A

    This is incorrect. Consider the test case
    [1,1,1,1,1,1,6]
    4

    The answer should be false while your solution output true


  • 0
    G

    I have same submission as posted here but have same doudt as @alcoholkid here. And the test case is failed.
    So my question is can we convert this problem to a knapsack question?


  • 0
    Z

    @alcoholkid Thanks for your test case. I modified the code, check again.

    public boolean canPartitionKSubsets(int[] nums, int k) {
            if (nums == null || nums.length == 0) {
                return false;
            }
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            if (sum % k != 0) {
                return false;
            }
            int target = sum / k;
            int[] dp = new int[target + 1];
            dp[0] = 1;
            for (int num : nums) {
                // each num should be smaller than the target
                if (num > target) {
                    return false;
                }
    
                for (int i = target; i >= num; i--) {
                    dp[i] += dp[i - num];
                }
            }
            return dp[target] >= k;
        }
    

  • 2
    A

    @zy084232 said in Java backpack solution:

    @alcoholkid Thanks for your test case. I modified the code, check again.

    public boolean canPartitionKSubsets(int[] nums, int k) {
            if (nums == null || nums.length == 0) {
                return false;
            }
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            if (sum % k != 0) {
                return false;
            }
            int target = sum / k;
            int[] dp = new int[target + 1];
            dp[0] = 1;
            for (int num : nums) {
                // each num should be smaller than the target
                if (num > target) {
                    return false;
                }
    
                for (int i = target; i >= num; i--) {
                    dp[i] += dp[i - num];
                }
            }
            return dp[target] >= k;
        }
    

    This is still incorrect. Check the test case
    [1,2,2,2,2]
    3
    Until now, I don't believe this problem can be solved as a backpack problem. In your dp, you want to find out # of possible subsets that sum to target. However, these subsets considered in your codes can have overlapping. Thus, even if # of possible subsets is larger than k, you can not necessarily conclude the original array can be portioned into k disjoint subsets with a sum equal to target.


Log in to reply
 

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