Java Solution


  • 0
    J

    The idea is to divide the int Array to 4 parts and each part's sum is totalsum/4. We can use the idea of dp to do so or just in this case using brute force and backtracking.

    public class Solution {
        public boolean makesquare(int[] nums) {
            int sum = 0;
            ArrayList<Integer> ns = new ArrayList();
            for(int i : nums){
                sum+=i;
                ns.add(i);
            }
            Collections.sort(ns,Collections.reverseOrder());
            if(sum%4!=0 || nums.length < 4) return false;
            else{
                int e = sum/4;
                return canDivide(ns,e,3);
            }
        }
        
        public boolean canDivide(ArrayList<Integer> nums,int target,int n){
            if(n == 0) return nums.size()>0;
            else{
                ArrayList<ArrayList<Integer>> ret = new ArrayList();
                divide(nums,target,ret,new ArrayList<Integer>(),0);
                for(ArrayList<Integer> left: ret){
                    //System.out.println(left + " --- "+ n);
                    if(canDivide(left,target,n-1)) return true;    
                }
                return false;
            }
        }
        
        public void divide(ArrayList<Integer> nums,int target,ArrayList<ArrayList<Integer>> ret, ArrayList<Integer> left,int start){
            if(target == 0){
                ArrayList<Integer> temp = new ArrayList(left);
                for(int i = start; i<nums.size();i++){
                    temp.add(nums.get(i));
                }
                ret.add(temp);
                return;
            }
            if(start >= nums.size()) return;
            
            
            
            if(target-nums.get(start) >= 0){
                divide(nums,target-nums.get(start),ret,left,start+1);
            }
            left.add(nums.get(start));
            divide(nums,target,ret,left,start+1);
            left.remove(left.size()-1);
        }
        
    }
    

Log in to reply
 

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