火柴拼正方形

说在前面

🎈每天进行一道算法题目练习，今天的题目是“火柴拼正方形”。

问题描述

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

思路分析

阅读完题目之后，我们知道了题目是要我们使用给出的若干根火柴拼接成一个正方形，拼接过程中有以下限制：

• 1、不能折断 任何一根火柴棒；
• 2、 每根火柴棒必须 使用一次

也就是说我们需要将所有火柴都用上，拼接连成一个正方形。\
知道了题目要求之后我们便可以开始思考该如何用代码实现，首先大家都知道正方形有以下两个的性质：

• 1、由四条边组成；
• 2、四条边的边长都相等

我们可以利用这两个性质来完成这道题目：

• 1、排除没有四条边或者边长不相等的情况

我们可以优先排除掉不能组成正方形的情况：

const sum = matchsticks.reduce((a,b) =>{return a + b;});
if (matchsticks.length < 4 && sum % 4) return false;

• 2、使用火柴填充四条边，判断是否可以刚好填充

将每根火柴尝试放入每一条边。
我们可以使用深搜回溯的方法来进行求解,每次遍历四条边，判断当前火柴可以放入哪一条边，如果四条边都不满足，无法放入火柴的话，则说明这组火柴不能组成火柴正方形。找到可以放入的边时，则递归判断下一根火柴，遇到不满足的情况时则回溯，具体代码如下：

function backtrack(i, bucket) {
    if (i >= matchsticks.length) return true;
    for (let j = 0; j < bucket.length; j++) {
        if (bucket[j] + matchsticks[i] > side) continue;
        bucket[j] += matchsticks[i];
        if (backtrack(i + 1, bucket)) return true;
        bucket[j] -= matchsticks[i];
    }
    return false;
}

AC代码

/**
 * @param {number[]} matchsticks
 * @return {boolean}
 */
var makesquare = function (matchsticks) {
    function backtrack(i, bucket) {
        if (i >= matchsticks.length) return true;
        for (let j = 0; j < bucket.length; j++) {
            if (bucket[j] + matchsticks[i] > side) continue;
            bucket[j] += matchsticks[i];
            if (backtrack(i + 1, bucket)) return true;
            bucket[j] -= matchsticks[i];
        }
        return false;
    }
    const sum = matchsticks.reduce((a,b) =>{return a + b;});
    const side = sum / 4;
    if (matchsticks.length < 4 && sum % 4) return false;
    matchsticks = matchsticks.sort((a, b) => b - a);
    const bucket = Array(4).fill(0);
    return backtrack(0, bucket);
};

说在后面

🎉这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。