Java DFS(backtrack) with sort first and check the largest number avoided the TLE 10 ms


  • 0
    L

    I saw a lot of dfs method got TLE after the new test cases added. I sorted the array from large to small and add a check to the largest number (if the largest number > sum/2) then false.

    class Solution {
        public boolean canPartition(int[] nums) {
            int sum = 0;
            int[] copy = Arrays.copyOf(nums, nums.length);
            Arrays.sort(copy);
            int j = nums.length -1;
            for(int i = 0; i< nums.length; i++){
                sum += copy[i];
                nums[j--] = copy[i];
            }
            if(sum%2!=0 ) return false;
            int target = sum/2;
            return subsetSum(nums, 0,0,target);
        }
        
        public boolean subsetSum(int[] nums, int startIndex, int sum, int target){
            if(sum > target){
                return false;
            }
            if(sum == target){
                return true;
            }
            
            for(int i = startIndex; i<nums.length;i++){
                boolean found = subsetSum(nums, i+1, sum + nums[i], target);
                if(found) return true;
                if(!found && i == 0) break;  // if the largest number > target, it is not true.
            }
            return false;
            
        }
    }
    

Log in to reply
 

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