Matchsticks to Square

题目来源
给一堆火柴，判断其能不能围成一个正方形。
我实在是太弱了，这都不会做。
DFS的方法，四条边，对于每个火柴，取或者不取，当四条边相等并且取完时候返回true。
中间有三个优化方案：

1. 可以先求出正方形边长，然后进行剪枝；
2. 将火柴长度从大到小排序，对于false的情况，可以更快的返回，这个优化很大！！！
3. 四条边，当前面几条边已经计算过当前长度是否可行的时候，就不需要再计算了。
   代码如下：

class Solution {
public:
    bool makesquare(vector<int>& nums) {
        if (nums.size() == 0)
            return false;
        vector<int> sideLength(4, 0);
        sort(nums.begin(), nums.end(), [](const int &l, const int &r) { return l > r; });
        int sum = 0;
        for (auto num : nums)
            sum += num;
        if (sum % 4 != 0)
            return false;
        return dfs(sideLength, nums, 0, sum / 4);
    }
    
    bool dfs(vector<int>& sideLength, vector<int>& nums, int cur, int target)
    {
        if (cur == nums.size())
            return  sideLength == vector<int>(4, sideLength[0]);
        for (int i=0; i<4; i++) {
            if (sideLength[i] + nums[cur] > target)
                continue;
                
            int j = i;
            while (--j >= 0) // third
                if (sideLength[i] == sideLength[j]) 
                    break;
            if (j != -1) continue;
            
            sideLength[i] += nums[cur];
            if (dfs(sideLength, nums, cur+1, target))
                return true;
            sideLength[i] -= nums[cur];
        }
        return false;
    }
};