8ms Java


  • 0
    A
    class Solution {
        public boolean canPartition(int[] nums) {
            int sum = 0;
            for (int i : nums) {
                sum += i;
            }
            if (sum % 2 == 1) return false;
            int s1 = (sum / 2) - nums[nums.length - 1];
            return canPart(nums, nums.length - 2, s1, sum / 2);
        }
        
        private boolean canPart(int[] nums, int end, int s1, int s2) {
            if (s1 < 0 || s2 < 0 || end < -1) return false;
            if (s1 == 0 && s2 == 0) return true;
            
            return canPart(nums, end - 1, s1 - nums[end], s2) || canPart(nums, end - 1, s1, s2 - nums[end]);
        }
    }
    

Log in to reply
 

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