Concise Java DFS solution


  • 0
    H
    public class Solution {
        public boolean makesquare(int[] nums) {
            if(nums == null || nums.length == 0) return false;
            
            int sum  = 0;
            for(int num : nums) sum+=num;
            
            if(sum%4!=0) return false;
           // sorting the list + using the list from end to start = sorting list DESC.
            Arrays.sort(nums);
            
            boolean[] mask = new boolean[nums.length];
            
            if(!findSum(sum/4, nums, mask, 0, nums.length-1)) return false;
            if(!findSum(sum/4, nums, mask, 0, nums.length-1)) return false;
            if(!findSum(sum/4, nums, mask, 0, nums.length-1)) return false;
            return true;
        }
        
        private boolean findSum(int target, int[] nums, boolean[] mask, int sum, int end)
        {
            if(sum==target) return true;
            if(sum>target) return false;
    
            for( int i = end ; i>=0 ; i--)
            {
                if(mask[i]) continue;
                mask[i]=true;
                if(findSum(target, nums, mask, sum+nums[i], i-1)) return true;
                else mask[i]=false;
            }
            return false;
        }
    }
    

Log in to reply
 

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