题目

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

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

示例 1:
image.png

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

示例 2:

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

提示:

  • 1 <= matchsticks.length <= 15
  • 1 <= matchsticks[i] <= 10^8

    解题方法

    递归回溯+剪枝

    通过递归的方式将每个火柴添加（除第一个）添加到每条边中并判断是否能够组成正方形。剪枝策略与 698. 划分为k个相等的子集 相同。
    时间复杂度O(n^4)，空间复杂度O(n)。
    C++代码： ```cpp class Solution { private: int average = 0;

public: bool backtracking(vector& matchsticks, vector& sides, int idx) { if(idx == matchsticks.size()) return true;

  1.     for(int i=0; i<4; i++) {
  2.         if(idx==0 && i>0)   continue;
  3.         if(sides[i]+matchsticks[idx]>average)   continue;
  4.         if(i>0 && sides[i]==sides[i-1]) continue;
  6.         sides[i] += matchsticks[idx];
  7.         if(backtracking(matchsticks, sides, idx+1))     return true;
  8.         sides[i] -= matchsticks[idx];
  9.     }
  10.     return false;
  11. }
  13. bool makesquare(vector<int>& matchsticks) {
  14.     if(matchsticks.size()<4)    return false;
  15.     for(int i=0; i<matchsticks.size(); i++) average+=matchsticks[i];
  16.     if(average%4)   return false;
  17.     average /=4;
  18.     vector<int> sides(4, 0);
  19.     return backtracking(matchsticks, sides, 0);
  20. }

};

<a name="Fbcnv"></a>
## 动态规划（状态压缩）
使用二进制表示每一个数字是否包含在集合中，则集合可以由一个整数表示，假设有`n`个数字，则可以构成`1<<n`个集合。使用动态数组`dp[i]`描述集合`i`的情况，其中`-1`表示不能划分为四个相等的子集，`0`表示能划分为四个相等的子集，其他数字代表正在填入边的当前大小。<br />则有如下递推关系：<br />![](https://cdn.nlark.com/yuque/__latex/2b011e575cd7430cf0ee7aaa073523e4.svg#card=math&code=%5Cbegin%7Balign%7D%0A%26%5Ctext%7Bif%7D%5C%3B%5C%3Bdp%5Bi-%281%3C%3Cj%29%5D%5Cge%200%5C%5C%0A%20%26%5Ctext%7Band%7D%20%5C%3B%5C%3B%20dp%5Bi-%281%3C%3Cj%29%5D%2Bmatchsticks%5Bj%5D%5Cle%20average%5C%5C%0A%26%5Ctext%7Bthen%7D%20%5C%3B%5C%3Bdp%5Bi%5D%20%3D%20%28dp%5Bi-%281%3C%3Cj%29%5D%2Bmatchsticks%5Bj%5D%5C%3B%5C%25%5C%3B%20average%2C%20%5Cquad%20%0A%5Cend%7Balign%7D&id=Z7InV)<br />如果`dp[(1<<n)-1]==0`则能够拼成正方形。<br />时间复杂度`O(n*2^n)`，空间复杂度`O(2^n)`。<br />**C++代码：**
```cpp
class Solution {
public:
    bool makesquare(vector<int>& matchsticks) {
        int len = matchsticks.size();
        if(len<4)    return false;

        int average = 0;
        for(int i=0; i<len; i++) average+=matchsticks[i];
        if(average%4)   return false;
        average /=4;

        sort(matchsticks.begin(), matchsticks.end());

        int size = (1<<len);
        vector<int> dp(size, -1);
        dp[0] = 0;
        for(int i=1; i<size; i++) {
            for(int j=0; j<len; j++) {
                if((i & (1<<j)) == 0)     continue;
                int pre = i & ~(1<<j);
                if(dp[pre]!=-1 && dp[pre]+matchsticks[j]<=average) {
                    dp[i] = (dp[pre]+matchsticks[j]) % average;
                    break;
                }  
            }
        }

        return dp[size-1]==0;
    }
};