Java cut branch fast solution


  • 0
    S
        public boolean makesquare(int[] nums) {
            int sum = 0, n = nums.length, i;
            if (n == 0)
                return false;
            
            for (i=0;i<n;i++)
                sum += nums[i];
            if (sum % 4 != 0)
                return false;
            int side = sum / 4;
            int[] remains = new int[] {side, side, side, side};
            Arrays.sort(nums);
                
            return canMake(nums, n-1, remains);
        }
        
        public boolean canMake(int[] nums, int index, int[] remains) {
            if (index < 0)
                return true;
            for (int i=0;i<4;i++) {
                if (remains[i] >= nums[index]) {
                    remains[i] -= nums[index];
                    if (canMake(nums, index-1, remains)) {
                        return true;
                    }
                    remains[i] += nums[index];
                }
            }
            return false;
        }
    }

Log in to reply
 

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