class Solution {
   //.火柴正方形 leetcode 473
    public boolean makesquare(int[] nums) {
         if (nums == null || nums.length<4) return false;
         int count = 0;
         for (int x:nums)
             count+=x;
         if (count%4 !=0) return false;

         int len = count/4;
         int k = 4; //.划分成4个等和子集
        Arrays.sort(nums);
       if (nums[nums.length-1]>len) return false;
       int beginIndex = nums.length-1;
       while (beginIndex>=0 && len == nums[beginIndex]){
           k--;
           beginIndex--;
       }
       int[] bucket = new int[k];

       return rec(nums,bucket,beginIndex,k,len);
    }

    private boolean rec(int[] nums,int[] bucket,int beginIndex,int k,int target){
        if (beginIndex<0)
            return true;

        int putnum = nums[beginIndex];

        for (int i =0;i<k;i++){
            if (putnum+bucket[i]<=target){
                bucket[i] += putnum;
                if (rec(nums,bucket,beginIndex-1,k,target)){
                    return true;
                }
                bucket[i] = bucket[i] - putnum;
                 if (bucket[i] == 0) break;
            }
        }
        return false;
    }
}