JAVA DP Solution, 34ms, 27 lines, with Detailed Explanation


  • 0

    Since the question asks for two subsets which have the same sum, we can calculate the sum of the whole array and then divide by two, as our target number, then the question becomes finding elements which sum up to the target number.

    If the sum is odd, then return false.

    If the sum is even, get the sum/2 as target number and use DP to check whether it exists or not.

    For example, [1,6,2,7]
    First, the sum is 16, our target number is 8.
    Second, let's select elements which sum up to 8.

    i. -> mark 1

    ii. -> mark 6, mark (1+6) = 7

    iii. -> mark 2, mark (1+2) = 3, mark (2+6) = 8 (here we already get the target number, so we can return true here), mark (2+7) = 9

    iiii. -> mark 7(already marked in ii), mark (7+1) =8 (already marked, also it's our target number). mark(7+6) = 13, mark(7+2) = 9(already marked), mark(7+7)=14, mark (7+3) = 10, mark (7+8) = 15, mark (7+9) = 16

    Since our target number is marked, return true for [1,6,2,7]

    public class Solution {
        public boolean canPartition(int[] nums) {
            int len = nums.length;
            if(len <= 1) return false;
            int sum = 0;
            for(int i = 0; i < len; i++){
                sum += nums[i];
            }
            if(sum % 2 == 1) return false;
            sum /= 2;
            int[] exist = new int[sum+1];
            exist[0] = 2;
            for(int i = 0; i < len; i++){
                for(int j = 0; j <= sum; j++){
                    if(exist[j] == 2 && j+nums[i] <= sum && exist[j+nums[i]] == 0){
                        exist[j+nums[i]] = 1;
                    }
                }
                for(int j = 1; j <= sum; j++){
                    if(exist[j] == 1) exist[j] = 2;
                }
                if(exist[sum] == 2)return true;
            }
            if(exist[sum] == 2)return true;
            return false;
        }
    }
    

Log in to reply
 

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