火柴拼正方形（回溯法实现）

题目：

你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。

如果你能使这个正方形，则返回 true ，否则返回 false 。

示例：

输入: matchsticks = [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。

输入: matchsticks = [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。

解题思路：

1.先对数组中所有火柴的长度进行求和sum

2.如果 sum不能被4等分，一定不能拼成正方形 ，返回false

3.若能被4等分，对数组按升序顺序排序

4.创建一个一维数组，为正方形的四条边，如果四条边都能被放满，说明可以拼成正方形

Code：

class Solution {
public:
   class Solution {
public:
    bool dfs(int index,vector<int> &matchsticks,vector<int>& edges,int len)
    {
        //如果此时下标已经来到了数组的长度，说明每根火柴都已经放完了，且能够拼成正方形，返回true
        if(index==matchsticks.size())
        {
            return true;
        }
        //开始拼4条边
        for(int i=0;isize();i++)
        {
            //如果当前的边+当前的火柴长度超过边长，则跳过
            if(edges[i]+matchsticks[index]>len)
            {
                continue;
            }
            //没有超过边长，则将这个火柴拼到当前边
            edges[i]+=matchsticks[index];
            //递归拼下一根火柴
            if(dfs(index+1,matchsticks,edges,len))
            {
                return true;
            }
            //回溯
            edges[i]-=matchsticks[index];
        }
        return false;
    }
    bool makesquare(vector<int> &matchsticks) {
        //对所有火柴长度求和（也就是总周长）
       int sum=accumulate(matchsticks.begin(),matchsticks.end(),0);
        //判断是否能被4整除
       if(sum%4!=0)
       {
           return false;
       }
        //排序
       sort(matchsticks.begin(),matchsticks.end());
        vector<int> edges(4);
        //传进去的参数为正方形的边长sum/4
        return dfs(0,matchsticks,edges,sum/4);
    }
};