leetcode473火柴拼正方形

[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);
    }
上一篇:python 装饰器(二):装饰器基础(二)变量作用域规则,闭包,nonlocal声明


下一篇:数据可视化之powerBI技巧(十七)在Power BI中对数据进行分组