beat 91% DFS convert to small search space


  • 0
    F
     public boolean makesquare(int[] nums) {
            if (nums.length < 4) return false;
            int sum  = 0;
            for (int num: nums) sum += num;
            if (sum%4 != 0) return false;
            boolean[] visited = new boolean[nums.length];
            Arrays.sort(nums);
            if (nums[nums.length-1] == 0) return false;
            return dfs(0, nums, visited, 0, sum/4, sum/4);
        }
        
        private boolean dfs(int pos, int[] nums, boolean[] visited, int layer, int target, int cTarget) {
            if (layer == 4) {
                return true;
            }
            if (target == 0) {
                return dfs(0, nums, visited, layer+1, cTarget, cTarget);// not ++, can't change the value
            }
            for (int i = pos; i < nums.length; i++) {
                if (!visited[i]) {
                    if (target-nums[i] < 0) return false;
                    visited[i] = true;
                    if (dfs(i+1, nums, visited, layer, target-nums[i], cTarget)) return true;
                    visited[i] = false;
                }
            }
            return false;
        }

Log in to reply
 

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