今日中等題：https://leetcode.cn/problems/matchsticks-to-square/
這題非常有意思病梢，第一次的思路比較簡單咒锻，以為可以排序后，用邊長減去tail祷蝌，再從head開始遍歷找剩下的火柴爽蝴，利用雙指針來做迅皇。
執(zhí)行了一下發(fā)現(xiàn)被這組測試數(shù)據(jù)教育了：[5,5,5,5,4,4,4,4,3,3,3,3] ，開始意識到事情并沒有這么簡單酵颁。
和然哥討論了半天嫉你，最后還是決定去看看題解，發(fā)現(xiàn)還是要利用遞歸材义，加上回溯的思路均抽，同時也要利用剪枝和貪心，最后才能得到一個不超時的答案其掂。
貼下代碼吧：
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;
}
// 火柴長度倒序油挥，在遍歷時從大的邊開始，優(yōu)化計算時間
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);
}
// 根據(jù)邊長遍歷全部火柴擺放
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;
}
}
