Use memory, time complicity is better than traditional 0/1 backpack method.


  • 0
    2
        public boolean canPartition(int[] nums) {
            int sum = 0;
            for(int i : nums)
                sum += i;
            if(sum % 2 == 1)
                return false;
            int [][] memo = new int[sum/2 + 1][nums.length]; 
            return help(nums, sum / 2, 0, memo);
        }
        private boolean help(int[] nums, int sum, int idx, int[][] memo) {
            
            if(sum < 0 || idx >= nums.length) {
                return false;
            }
            if(sum == 0) {
                 
                return true;
            }
            
            if(memo[sum][idx] != 0) {
                return memo[sum][idx] == 1;
            }
            boolean ans = help(nums, sum - nums[idx], idx + 1, memo) || help(nums, sum, idx + 1, memo);
            if(ans) {
                memo[sum][idx] = 1;
            }else {
                memo[sum][idx] = 2;
            }
            return ans;
            
        }
    

Log in to reply
 

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