Recursive (DFS) Java solution (10ms), O(n) space, no DP


  • 0
    A

    This solution sorts the array before recursing over the sorted array in reverse order (because there's no convenient way to sort an array of ints in descending order). At each step of the recursion, we check if the goal (half of the sum of the array) has been hit, or if it has been exceeded. Checking larger numbers first is ideal for longer arrays and also when the sum is large.

        public boolean canPartition(int[] nums) {
            if(nums.length == 0) return true;
            if(nums.length == 1) return nums[0] == 0;
            
            Arrays.sort(nums);
            
            int sum = 0;
            for(int i : nums) {
                sum += i;
            }
            if(sum % 2 == 1) return false;
            int goal = sum/2;
            
            return helper(nums, nums.length-1, goal);
        }
        
        public boolean helper(int[] nums, int index, int sum) {
            if(sum < 0) return false;
            if(sum == 0) return true;
            for(int i = index; i >= 0; i--) {
                if(helper(nums, i-1, sum - nums[i])) {
                    return true;
                }
            }
            return false;
        }
    

Log in to reply
 

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