2022-06-02 「473. 火柴拼正方形」

今日中等题：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;
    }
}