[LeetCode] Matchsticks to Square

1. 使用4个数的数组分别记录每条边的增长情况

2. 遍历数组，如果一条边加上遍历的数不会超过划分边长，则加入这条边。

3. 递归处理下一个数。终止条件是遍历完后，4条边长度相等，返回true，否则返回false。

如果递归结果为false，则加步骤2中遍历到的数加入另外一条边，继续递归。

4. 一个加速的措施是遍历之前先将数组按照降序排列，这样每次选择是都优先选择较大的树加入一条边，时间复杂度降低。

class Solution { public:     static bool comFunc(int a, int b) {         return a > b;     }     bool makesquare(vector<int>& nums) {         int n = nums.size();         if (n == 0) {             return false;         }         int sumNum = 0;         for (int i = 0; i < n; i++) {             sumNum += nums[i];         }         if (sumNum % 4 != 0) {             return false;         }         print_vec(nums);         sort(nums.begin(), nums.end(), comFunc);         print_vec(nums);         vector<int> sums = vector<int>(4, 0);         return dfs(nums, sums, 0, sumNum / 4);     }     bool dfs(vector<int>& nums, vector<int>& sums, int index, int target) {         if (index == nums.size()) {             if (sums[0] == target && sums[1] == target && sums[2] == target && sums[3] == target) {                 return true;             }             return false;         }         for (int i = 0; i < 4; i++) {             if (sums[i] + nums[index] > target) continue;             sums[i] += nums[index];             if (dfs(nums, sums, index+1, target)) return true;             sums[i] -= nums[index];         }         return false;     } };