火柴拼正方形

/*
 * 思路：
 * 1. 计算所有火柴的总长度，如果不是4的倍数则返回false。
 * 2. 计算每条边的目标长度。
 * 3. 使用回溯法将火柴分成4组，每组的长度等于目标长度。
 * 4. 使用Java Stream简化数组的处理。
 */
import java.util.stream.IntStream;
import java.util.Arrays;
 
public class Solution {
    public boolean makesquare(int[] matchsticks) {
        int totalLength = IntStream.of(matchsticks).sum();
        if (totalLength % 4 != 0) return false;
        int targetLength = totalLength / 4;
        matchsticks = IntStream.of(matchsticks).boxed().sorted((a, b) -> b - a).mapToInt(i -> i).toArray();
        int[] sides = new int[4];
        return backtrack(matchsticks, sides, targetLength, 0);
    }
 
    private boolean backtrack(int[] matchsticks, int[] sides, int targetLength, int index) {
        if (index == matchsticks.length) {
            return Arrays.stream(sides).allMatch(side -> side == targetLength);
        }
        for (int i = 0; i < 4; i++) {
            if (sides[i] + matchsticks[index] <= targetLength) {
                sides[i] += matchsticks[index];
                if (backtrack(matchsticks, sides, targetLength, index + 1)) return true;
                sides[i] -= matchsticks[index];
            }
        }
        return false;
    }
}