Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.
Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.
Example 1:
Input: [1,1,2,2,2] Output: true Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.Example 2:
Input: [3,3,3,3,4] Output: false Explanation: You cannot find a way to form a square with all the matchsticks.Note:
The length sum of the given matchsticks is in the range of 0 to 10^9.The length of the given matchstick array will not exceed 15. 解析：求数组存不存在4个子数组，他们的和相等，求法也相当于暴力递归的解法，求出来边长，对数组进行从大到小的排序有助于加速，判断当前元素是否大于边长和把数组当前元素放入一个边判断是否超出边长，如果放入四个边都超出边长则返回到上次边长记录点。
代码：
class Solution { public: bool makesquare(vector<int>& nums) { if (nums.empty()) return false; int zhouchang=0; for (int i=0; i<nums.size(); i++) { zhouchang+=nums[i]; } if (zhouchang%4) return false; int bian=zhouchang/4; vector<bool>vis(nums.size(),false); sort(nums.begin(),nums.end(),greater<int>()); vector<int>sizhou(4,0); bool ans=dfs(nums,sizhou,bian,0); return ans; } bool dfs(vector<int>&nums,vector<int>&sizhou,int bian, int begin) { if (begin==nums.size()) return true; { if (nums[begin]>bian) return false; int flag=0; for (int k=0; k<4; k++) { if ((sizhou[k]+nums[begin])<=bian) { flag++; sizhou[k]+=nums[begin]; bool res=dfs(nums,sizhou,bian,begin+1); if (res) return true; sizhou[k]-=nums[begin]; } } return false; } } };
