今日中等题：https://leetcode.cn/problems/matchsticks-to-square/
这题非常有意思，第一次的思路比较简单，以为可以排序后，用边长减去tail，再从head开始遍历找剩下的火柴，利用双指针来做。
执行了一下发现被这组测试数据教育了：[5,5,5,5,4,4,4,4,3,3,3,3] ，开始意识到事情并没有这么简单。
和然哥讨论了半天，最后还是决定去看看题解，发现还是要利用递归，加上回溯的思路，同时也要利用剪枝和贪心，最后才能得到一个不超时的答案。
贴下代码吧：
class Solution {
public boolean makesquare(int[] matchsticks) {
// 求正方形周长
int sum = 0;
int length = matchsticks.length;
for(int i = 0; i < length; i++) {
sum += matchsticks[i];
}
Arrays.sort(matchsticks);
if (sum % 4 !=0 || matchsticks[length-1] > sum / 4) {
return false;
}
// 火柴长度倒序，在遍历时从大的边开始，优化计算时间
int tmp = 0;
for (int j = 0; j < length / 2; j++) {
tmp = matchsticks[j];
matchsticks[j] = matchsticks[length - 1 - j];
matchsticks[length - 1 - j] = tmp;
}
int[] squ = new int[4];
// 递归
return dfs(0, matchsticks, squ, sum/4);
}
// 根据边长遍历全部火柴摆放
public boolean dfs(int head, int[] matchsticks, int[] squ, int len) {
if (head == matchsticks.length) {
return true;
}
for (int i = 0; i < squ.length; i++) {
squ[i] += matchsticks[head];
if (squ[i] <= len && dfs(head + 1, matchsticks, squ, len)) {
return true;
}
squ[i] -= matchsticks[head];
}
return false;
}
}
