473. 火柴拼正方形

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/matchsticks-to-square
首先分析题意，需要判断给定的数组能否组成正方形。

于是有了以下分析：

1.当数组总和不能整除4则不可能组成正方形，返回False

2.当数组的长度小于4也不可能组成正方形，返回False

3.当数组中的最大值大于正方形边长不可能组成正方形，返回False

4.其余情况可能符合条件：

那么怎么才能判断出数组是否能够组成正方形，一个直观的反映是每条边都试试数组中的值，然后找到符合题意的一个组合即可，即暴力搜索--与回溯方法不谋而合，于是我这里使用的是回溯法。

依次在四条边上放入数组中的每个值，判断其长度是否满足边长，如果数组中所有的值都放置完成，则代表满足，否则不满足。

结合官方给出的参考答案写出如下代码

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        side_length = sum(matchsticks) // 4
        if sum(matchsticks) % 4 != 0 or len(matchsticks) < 4 or max(matchsticks) > side_length:
            return False
        matchsticks.sort(reverse = True) #数组从大到小排列，缩小搜索次数
        side = [0] * 4 #创建四条边
        def dfs(index):
            if index == len(matchsticks): #数组每个值都放置完成则代表找到满足题意的组合，返回True
                return True
            for i in range(4): #将数组中的值依次放入四条边判断
                side[i] += matchsticks[index]
                if side[i] <= side_length and dfs(index + 1): #如果当前边的值小于等于给定的边长，且依次往下遍历均能满足则返回Ture
                    return True
                side[i] -= matchsticks[index] #回溯，去掉当前值，即当找到不满足条件的值时，拿出火柴，回到未放置的状态
            return False
        return dfs(0)
        

提交查看通过

搜索

复制