15ms JAVA DFS solution


  • 1
    public boolean makesquare(int[] nums) {
            if (nums.length < 4) {
                return false;
            }
            Arrays.sort(nums);
            int sum = 0;
            int max = 0;
            for ( int num : nums) {
                sum += num;
                max = Math.max(max, num);
            }
            
            int len = sum / 4;
            if (sum % 4 != 0 || max > len) {
                return false;
            }
            boolean[] isUsed = new boolean[nums.length];
    
            for (int i = 0; i < 4; i++) {
                boolean flag = dfs(isUsed, nums, len, nums.length - 1);
                if (!flag) {
                    return false;
                }
            }
            return true;
        }
    
        private boolean dfs(boolean[] isUsed, int[] nums, int target,int start) {
            if (target < 0) {
                return false;
            }
            if (target == 0) {
                return true;
            }
            for (int i = start; i >= 0; i--) {
                if (!isUsed[i]) {
                    isUsed[i] = true;
                    boolean flag = dfs(isUsed, nums, target - nums[i], i - 1);
                    if (flag) {
                        return true;
                    } else {
                        isUsed[i] = false;
                    }
                }
            }
            return false;
            
        }
    

  • 0
    Y

    @YipqiY
    some optimization, if nums sort, max should be nums[len-1].


Log in to reply
 

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