[1,1,2,2,2]
可以拼成一个正方形[1+1,2,2,2]
思想:
1.木桶法,把四个边当作四个木桶,从数组大的一端开始装入木桶,一直装到avg
2.回溯,每个数组元素可以装在木桶里。也可以不装在木桶里让下一个木桶装。
bool make_sq(vector<int>& nums,vector<int>& count,int begin,int end,int avg)
{
if(begin==end&&count[0]==avg&&count[1]==avg&&count[2]==avg&&count[3]==avg)
return true;//退出条件
int i;
for(i=0;i<4;i++)//路径选择
{
if(count[i]+nums[end]<=avg)//必须有等号,不然没法进入下一个木桶的循环,这里是个剪枝
{
count[i]=count[i]+nums[end];//如果当前木桶装
if(make_sq(nums,count,begin,end-1,l))
return true;
count[i]=count[i]-nums[end];//如果当前木桶不装
}
}
return false;
}
bool makesquare(vector<int>& nums) {
long long sum=0;
int len=nums.size(),i;
if(len<4)
return false;
for(i=0;i<len;i++)
sum=sum+nums[i];
if(sum%4!=0)
return false;
long long l=sum%4;
sort(nums.begin(),nums.end());
vector<int> count;
for(i=0;i<4;i++)
count.push_back(0);
return make_sq(nums,count,-1,len-1,sum/4);
}