Java Solution similar to 'Subset Sum Problem'


  • 10

    It's similar to Subset Sum Problemwhich asks us to find if there is a subset whose sum equals to target value. For this problem, the target value is exactly the half of sum of array. Let's see the code.

    public class Solution {
        public boolean canPartition(int[] nums) {
            int sum = 0;
            for(int num: nums) sum += num;
            if(sum % 2 == 1) return false;
            
            int target = sum / 2;
            boolean[][] dp = new boolean[nums.length][target + 1];
            // deal with the first row
            if(nums[0] <= target) dp[0][nums[0]] = true;
            
            // deal with the first col
            for(int i = 0; i < nums.length; i++) dp[i][0] = true;
            
            // deal with the rest
            for(int i = 1; i < dp.length; i++) {
                for(int j = 1; j < dp[0].length; j++) {
                    if(j < nums[i]) {
                        dp[i][j] = dp[i - 1][j];
                    } else {
                        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                    }
                }
            }
            return dp[dp.length - 1][dp[0].length - 1];
        }
    }
    

  • 0
    L

    We have a similar plan. Your code inspire me a lot , thanks


  • 0
    A

    @xietao0221 Thanks for your solution . In your solution, just after the line
    if(nums[0] <= target) dp[0][nums[0]] = true;, I think you can add

    else
          false;
    

    Then it would avoid the dp calculation for test cases like 26,13,1. Any thoughts ? Let me know if I am missing something.


Log in to reply
 

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