今日中等題：https://leetcode.cn/problems/matchsticks-to-square/

這題非常有意思，第一次的思路比較簡單，以為可以排序后，用邊長減去tail，再從head開始遍歷找剩下的火柴，利用雙指針來做。
執(zhí)行了一下發(fā)現(xiàn)被這組測試數據教育了：[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);
    }

    // 根據邊長遍歷全部火柴擺放
    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;
    }
}