Java Solution with backtracking beat 97%


  • 0
    L
    public class Solution {
        private boolean find(int[] nums, int pos, int targ){
            if(targ == 0) return true;
            if(targ < 0) return false;
            for(int i=pos; i>=0; i--){
                int cur = nums[i];
                if(cur > 0){
                    nums[i] = -cur;
                    boolean flag = find(nums, i - 1, targ - cur);
                    if(flag) return true;
                    nums[i] = cur;
                }
            }
            return false;
        }
        public boolean makesquare(int[] nums) {
            int sum = 0;
            for(int num : nums) sum += num;
            if((sum & 3) != 0) return false;
            int edge = sum >> 2, len = nums.length;
            Arrays.sort(nums);
            int count = 0;
            for(int j=len - 1; j>=0; j--){
                if(nums[j] > 0){
                    boolean flag = find(nums, j - 1, edge - nums[j]);
                    if(!flag) return false;
                    if(++count == 3) return true;
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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