java dfs


  • 0
    C
    public boolean makesquare(int[] nums) {
            int sum = 0;
            if(nums == null || nums.length == 0) return false;
            for(int i : nums){
                sum += i;
            }
            if(sum % 4 != 0) return false;
            Arrays.sort(nums);
            return helper(nums, 0, new boolean[nums.length], 0, sum/4,0);
        }
        private boolean helper(int[] nums, int count, boolean[] used, int val, int target, int index){
            
            if(val == target){
                count ++;
                if(count == 4) return true;
                return helper(nums, count, used, 0, target,0);
            }
            for(int i = index; i < nums.length; i++){
                if(used[i]) continue;
                if(val + nums[i] > target) break;
                val += nums[i];
                used[i] = true;
                if(helper(nums, count, used, val, target, i+1)) return true;
                used[i] = false;
                val -= nums[i];
            }
            return false;
        }

Log in to reply
 

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