Java solution with backtracking


  • 0
    Y

    The basic idea: for each match, try to put it on line 0, 1, 2 or 3, and recursively put the other matches. Anytime, if one line is longer than sum / 4, backtrack.

    public class Solution {
        static public boolean makesquare(int[] nums) {
            if (nums == null || nums.length < 4)
                return false;
                
            int sum = 0; 
            for (int i = 0; i < nums.length; i++)
                sum += nums[i];
                
            if (sum % 4 != 0)
                return false;
    
            return helper(new int[4], sum / 4, nums, 0);
        }
        
        static private boolean helper(int[] lines, int len, int[] nums, int index) {
            if (index == nums.length) {
                if (lines[0] == len && lines[1] == len && lines[2] == len)
                    return true;
    
                return false;
            }
            
            for (int i = 0; i < 4; i++) {
                if (lines[i] + nums[index] > len)
                    continue;
                lines[i] += nums[index];
    
                if (helper(lines, len, nums, index + 1))
                    return true;
                    
                lines[i] -= nums[index];
            }
            return false;
        }
    }
    

    First, I solved the problem checking every permutation of the match combinations, but got Time Limit Exceeded error.

        public boolean makesquare(int[] nums) {
            if (nums == null || nums.length < 4)
                return false;
            int sum = 0; 
            int n = nums.length;
            for (int i = 0; i < n; i++)
                sum += nums[i];
                
            if (sum % 4 != 0)
                return false;
                
            int len = sum / 4;
            int x = 3;
            for (int i = 1; i < n; i++)
                x = (x << 2) + 3;
    
            for (int i = 1; i <= x; i++) {
                int[] lines = new int[4];
                for (int j = 0; j < 15 && j < n; j++) {
                    lines[(i >> (j * 2)) % 4] += nums[j];
                }
                if (lines[0] == len && lines[1] == len && lines[2] == len && lines[3] == len)
                    return true;
            }
            return false;
        }
    

  • 0

    I ran this exact same code in Python and got TLE. Can the mods please fix the judge? This should not be happenning.


  • 0
    Y

    @Donald-J.-Trump

    I agree with you, President-elect:-) It's very easy to get TLE, even it's in java. If I change the order of code lines, it may cause TLE.


Log in to reply
 

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