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

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

示例 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); } };