Java 15ms DFS Solution


  • 0
    1. Sort the array
    2. If this matchstick is used, then set it to negative
    3. Run the dfs for four times
    public class Solution {
        public boolean makesquare(int[] nums) {
            int sum = 0;
            int n = nums.length;
            if(n < 4) return false;
            Arrays.sort(nums);
            for(int i = 0; i < n; i++){
                sum += nums[i];
            }
            if(sum == 0 || sum % 4 != 0) return false;
            int side = sum/4;
            for(int j = 0; j < 4; j++){
                for(int i = n - 1; i >= 0; i--){
                    if(nums[i] > 0){
                        if(side < nums[i] || !dfs(side, nums, i))return false;
                    }
                }
            }
            for(int i = 0; i < n; i++){
                if(nums[i] > 0)return false;
            }
            return true;
        }
        public boolean dfs(int target, int[] nums, int cur){
            if(target == 0)return true;
            for(int i = cur; i >= 0; i--){
                if(nums[i] > 0 && nums[i] <= target){
                    nums[i] = -nums[i];
                    if(dfs(target + nums[i], nums, i-1))return true;
                    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.