Java 13ms solution - beats 99.15% Java solution


  • 1
    E

    Key point: Find edge for 4 times, each time containing the longest match of all matches left. So simply call the recursive function - findEdge() 4 times, whenever a next edge is unavailable, return false; else update nums array and find next edge. (Those numbers already used for constructing edges could be set to 0 so that they won't affect later edges.)

    ps: seems like checking sum % 4 != 0 and the longest match is no longer than sum / 4 first saves a lot of time.

    public class Solution {

    private int[] resNums;
    
    public boolean makesquare(int[] nums) {
        resNums = new int[nums.length];
        if (nums.length == 0) return false;
        
        Arrays.sort(nums); 
        
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        
        if (sum % 4 != 0) return false;
        int edgeLen = sum / 4;
        
        for (int i = 0; i < 4; i++) {
            resNums = new int[nums.length];
            
            int start = nums.length - 1;
            while(nums[start] == 0) start--;
            if (findEdge(nums, edgeLen, start, 0) == false) return false;
        
            nums = resNums;
        }
        return true;
    }
    
    private boolean findEdge(int[] nums, int len, int start, int temp) {
        if (temp == len) {
            resNums = nums;
            return true;
        }
        
        for (int i = start; i >= 0; i--) {
            if (temp + nums[i] <= len) {
                
                temp += nums[i];        
                int memo = nums[i];
                nums[i] = 0;
    
                if (findEdge(nums, len, i - 1, temp)) return true;
                
                else {
                    nums[i] = memo;
                    temp -= nums[i];
                }
            }
        }
        return false;
    }
    

    }


  • 0
    L

    good solution! Same idea, shorter code:

    public class Solution {
        public boolean makesquare(int[] nums) {
            if (nums.length == 0) return false;
    
            Arrays.sort(nums); 
    
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
    
            if (sum % 4 != 0) return false;
            int edgeLen = sum / 4;
    
            for (int i = 0; i < 4; i++) {
                int start = nums.length - 1;
                if (!findEdge(nums, edgeLen, start)) return false;
            }
            return true;
        }
    
        private boolean findEdge(int[] nums, int remain, int start) {
            if (remain == 0) {
                return true;
            } else if(remain < 0) {
                return false;
            }
    
            for (int i = start; i >= 0; i--) {
                if (nums[i] > 0) {
                    nums[i] = -nums[i];
                    if (findEdge(nums, remain + nums[i], i - 1)) {
                        return true;
                    }
                    else {
                        nums[i] = -nums[i];
                    }
                }
            }
            
            return false;
        }
    }
    

Log in to reply
 

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