leetcode473 火柴拼正方形 中等

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

示例 1:

输入: [1,1,2,2,2]
输出: true

解释: 能拼成一个边长为2的正方形，每边两根火柴。
示例 2:

输入: [3,3,3,3,4]
输出: false

解释: 不能用所有火柴拼成一个正方形。
注意:

给定的火柴长度和在 0 到 10^9之间。
火柴数组的长度不超过15。

思路

• 每一条边的长度肯定为一样的，即长度为sum/4
• 将火柴长度由大到小排序，先将大的放好，可以减少很多的尝试次数，因为不合适的大多都是较小的火柴
• 用dfs遍历数组，将他们放到第 i 条边上，如果第 i 条边加上这个数之后超过了sum/4，则肯定得放在下一条边
• 如果遍历完数组了，并没有能够凑出合适的四条边，则肯定是之前的火柴放错了边，所以需要回溯到上一步，尝试下一条边。。。
• 直到能够凑出合适的四条边，返回true
  

class Solution {
private:
    bool dfs(vector<int>&nums,int bucket[],int j,int targe){
        if(j>=nums.size())
            return bucket[0]==targe&&bucket[1]==targe&&bucket[2]==targe&&bucket[3]==targe; 
        for(int i=0;i<4;i++){
            if(bucket[i]+nums[j]>targe){
                continue;
            }
            bucket[i] += nums[j];
            if(dfs(nums,bucket,j+1,targe))
                return true;
            bucket[i] -= nums[j];
        }
        return false;
    }
public:
    bool makesquare(vector<int>& nums) {
        if(nums.size()<4)
            return false;
        int sum=0;
        for(int i=0;i<nums.size();i++){
            sum += nums[i];
        }
        if(sum % 4 )
            return false;
        sort(nums.rbegin(),nums.rend());
        int bucket[4]={0};
        return dfs(nums,bucket,0,sum/4);
    }
};