473. 火柴拼正方形

题目

你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。

如果你能使这个正方形，则返回 true ，否则返回 false 。

示例 1:

输入: matchsticks = [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。

示例 2:

输入: matchsticks = [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。

提示:

1 <= matchsticks.length <= 15
1 <= matchsticks[i] <= 10^8

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/matchsticks-to-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

题目翻译下就是说给定一个数组，能否将其划分为四个和相同的子数组。

可以使用暴力搜索的方法，定义一个大小为4的数组nums，将matchsticks数组的值依次试着放入nums的四个位置。

nums[i]加matchsticks[i]如果不超过sum/4，就先暂时将matchsticks[i]放入nums[i]，然后继续考虑matchsticks[i+1]，直到找到一种可以成功划分的方法，或者找不到返回false。

代码

class Solution {
    boolean ans = false;
    int sum = 0;
    public boolean makesquare(int[] matchsticks) {
        int n = matchsticks.length;
        sum = Arrays.stream(matchsticks).sum();
        if (sum % 4 != 0) {
            return false;
        }
        int[] edges = new int[4];
        // 这里将matchsticks降序排列，比升序排列可以更快找到解
        Arrays.sort(matchsticks);
        for (int i = 0, j = n - 1; i < j; i++, j--) {
            int tmp = matchsticks[i];
            matchsticks[i] = matchsticks[j];
            matchsticks[j] = tmp;
        }
        dfs(0, edges, matchsticks, n);
        return ans;
    }
    private void dfs(int index, int[] edges, int[] matchsticks, int n) {
        // ans为true就不用再继续了，对于题目的测试用例，加上这句可以快很多
        if (ans) {
            return;
        }
        if (index == n) {
            ans = true;
            return;
        }
        // 试着将matchsticks[i]放入不满的edge中
        for (int i = 0; i < 4; i++) {
            if (edges[i] + matchsticks[index] <= sum / 4) {
                edges[i] += matchsticks[index];
                dfs(index + 1, edges, matchsticks, n);
                edges[i] -= matchsticks[index];
            }
        }
    }
}