广联达4.29笔试,第四题（钢筋（火柴）拼正方形）

实际上这道题等价于leetcode上的2道原题，将能否将集合划分为为k个等和子集或火拆拼正方形

前者是后者的一般形式

后者中k=4(因为正方形是四条边)

原始思路就是构建k个bucket，将数组nums中的元素依次试探性装入buket，最后判断是否能装够k个bucket且每个bucket中的数值和相等

优化就是预处理+回溯中的break：先对nums排序，从后往前遍历，如果nums[i] == len(这里指正方形边长) ，则k--

package GuangLianDa;

import java.util.*;

public class Main4 {



    //.火柴正方形 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){
                if (rec(nums,bucket,beginIndex-1,k,target)){
                    return true;
                }
                bucket[i] = bucket[i] - putnum;
                if (bucket[i] == 0) break;
            }
        }
        return false;
    }

}