leetcode473. 火柴拼正方形

分析

要组成正方形，那么要生成四条一样的边，相当于把n个火柴放到四个桶中，将总数和全部加起来，如果不能被4整除，说明不能均匀分配，返回false。否则进行dfs遍历，往每个桶中放入火柴。

class Solution {
public:
    bool dfs(int cur,int target,vector<int>& matchsticks,vector<int>&bucket){
        if(cur>=matchsticks.size())
            return(bucket[0]==target&&bucket[1]==target&&bucket[2]==target);
        for(int i=0;i<4;i++){
            if(bucket[i]+matchsticks[cur]>target)continue;
            bucket[i]+=matchsticks[cur];
            if(dfs(cur+1,target,matchsticks,bucket))return true;
            bucket[i]-=matchsticks[cur];
        }
        return false;
    }
    bool makesquare(vector<int>& matchsticks) {
      if(matchsticks.size()<4)return false;
      int sum=accumulate(matchsticks.begin(),matchsticks.end(),0);
      if(sum%4)return false;
      sort(matchsticks.begin(),matchsticks.end(),greater<int>());
      vector<int> bucket(4);
      return dfs(0,sum/4,matchsticks,bucket);
    }
};