火柴拼正方形

473. 火柴拼正方形 - 力扣（LeetCode）

你将得到一个整数数组 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] <= 108

解题思路

本体思路同698. 划分为k个相等的子集，采用回溯算法，相当于有4个容量相同的桶，把小球放入这四个桶中，如果所有的小球都能放入这四个桶，说明可以拼成正方形。
如图，站在小球的视觉，每个小球可以放入任意的桶，桶的容量为totalLen/4，每一层代表每个小球的选择，若找到一条能放满小球的路径，返回true，为了减少搜素次数，matchsticks数组进行逆序排序。

代码：

class Solution {
    public static boolean makesquare(int[] matchsticks) {
        matchsticks = Arrays.stream(matchsticks).boxed().
                sorted((a, b) -> b - a).mapToInt(Integer::intValue).toArray(); //降低排序,减少搜索次数
        int sum = Arrays.stream(matchsticks).sum();
        if(sum % 4 != 0) return false;
        int len  = sum / 4;
        int[] edges = new int[4]; //存放4条边
        return traversal(matchsticks, edges, len, 0);


    }
    
    
    public static boolean traversal(int[] matchticks, int[] edges, int len, int index){
        //能遍历所有边，说明已经放入了相应的桶
        if(index == matchticks.length){
            return true;
        }

        for(int i = 0; i < 4; i++){ //横向遍历桶
            if(edges[i] + matchticks[index] > len){ //如果该桶放不下，就换下一个桶放
                continue;
            }else{ //放入边
                edges[i] += matchticks[index];
                if(traversal(matchticks, edges, len, index + 1)){
                    return true;
                }
                edges[i] -= matchticks[index];
            }
        }
        return false;
    }
}

• 时间复杂度：$O(4^n)$，其中 n 是火柴的数目。每根火柴都可以选择放在 4 条边上
• 空间复杂度：$O(n)$，n为递归栈需要的空间