LeetCode 374 火柴拼正方形[回溯] HERODING的LeetCode之路

解题思路：
首先火柴的总长度得满足4的倍数，否则根本不能构成正方形，接着对每个火柴进行dfs，让其在每条边都试一次，并回溯，如果所有的火柴都遍历并满足构成正方形的条件，返回true，否则返回false，代码如下：

class Solution {
public:
    bool makesquare(vector& matchsticks) {
        int count = accumulate(matchsticks.begin(), matchsticks.end(), 0);
        if(count % 4 != 0) {
            return false;
        }
        sort(matchsticks.begin(), matchsticks.end(), greater());
        vector edges(4);
        return dfs(0, matchsticks, edges, count / 4);
    }

    bool dfs(int index, vector& matchsticks, vector& edges, int num) {
        if(index == matchsticks.size()) {
            return true;
        }
        for(int i = 0; i < 4; i ++) {
            edges[i] += matchsticks[index];
            if(edges[i] <= num && dfs(index + 1, matchsticks, edges, num)) {
                return true;
            } 
            edges[i] -= matchsticks[index];
        }
        return false;
    }
};