題目來源
給一堆火柴，判斷其能不能圍成一個(gè)正方形。
我實(shí)在是太弱了，這都不會(huì)做。
DFS的方法，四條邊，對(duì)于每個(gè)火柴，取或者不取，當(dāng)四條邊相等并且取完時(shí)候返回true。
中間有三個(gè)優(yōu)化方案：

1. 可以先求出正方形邊長(zhǎng)，然后進(jìn)行剪枝；
2. 將火柴長(zhǎng)度從大到小排序，對(duì)于false的情況，可以更快的返回，這個(gè)優(yōu)化很大?。。?/li>
3. 四條邊，當(dāng)前面幾條邊已經(jīng)計(jì)算過當(dāng)前長(zhǎng)度是否可行的時(shí)候，就不需要再計(jì)算了。
   代碼如下：

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;
    }
};