Java sort + three times of DFS solution


  • 0
    D
    public class Solution {
        public boolean makesquare(int[] nums) {
            if (nums == null || nums.length < 4) {
                return false;
            }
            Arrays.sort(nums);
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            if (sum % 4 != 0) {
                return false;
            }
            int side = sum / 4;
            if (nums[nums.length - 1] > side) {
                return false;
            }
            Set<Integer> vIndices = new HashSet<>();
            for (int i = 0; i < 3; i++) {
                if (!dfs(nums, nums.length - 1, 0, side, vIndices)) {
                    return false;
                }
            }
            return true;
        }
    
        private boolean dfs(int[] nums, int index, int sum, int side, Set<Integer> vIndices) {
            assert index >= 0;
            assert sum < side;
            if (!vIndices.contains(index) && sum + nums[index] <= side) {
                vIndices.add(index);
                if (sum + nums[index] == side || (index > 0 && dfs(nums, index - 1, sum + nums[index], side, vIndices))) {
                    return true;
                } else {
                    vIndices.remove(index);
                }
            }
            return index > 0 && dfs(nums, index - 1, sum, side, vIndices);
        }
    }
    

Log in to reply
 

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