Matchsticks to Square,LeetCode,473

LeetCode 473题 “Matchsticks to Square” 是一个中等难度的题目，主要考察的是回溯算法和深度优先搜索（DFS）。题目要求我们判断是否可以用一组火柴棍组成一个正方形。每根火柴棍的长度都是给定的，并且我们可以使用每根火柴棍一次。

题目描述

给定一个整数数组 nums，其中每个元素代表一根火柴棍的长度。你需要判断是否可以将这些火柴棍排列成一个正方形。

示例

示例 1:

输入: [1,1,2,2,2] 输出: true

解释: 可以组成一个边长为2的正方形，正方形的四条边分别是 {1,1}, {2}, {2}, {2}。

示例 2:

输入: [3,3,3,3,4] 输出: false

解释: 无法将这些火柴棍组成一个正方形。

解题思路

1. 计算总和和边长：
   • 首先计算所有火柴棍的总长度 sum。
   • 如果 sum 不是4的倍数，直接返回 false，因为无法分成四条相等的边。
   • 计算每条边的长度 side = sum / 4。
2. 排序：
   • 将火柴棍按长度从大到小排序，这样可以更快地发现不满足条件的情况。
3. 回溯算法：
   • 使用深度优先搜索（DFS）尝试将火柴棍分配到四条边上。
   • 维护一个数组 sides，表示当前四条边的长度。
   • 逐个尝试将火柴棍放入某一条边，如果某条边的长度超过了 side，则回溯。
4. 剪枝优化：
   • 如果某根火柴棍的长度超过了 side，直接返回 false。
   • 如果当前边的长度为0，则优先放入当前边，这样可以减少不必要的搜索。

代码实现

class Solution: def makesquare(self, nums: List[int]) -> bool: if not nums: return False

    total_length = sum(nums)
    if total_length % 4 != 0:
        return False

    side_length = total_length // 4
    nums.sort(reverse=True)

    if nums[0] > side_length:
        return False

    sides = [0] * 4

    def dfs(index):
        if index == len(nums):
            return sides[0] == sides[1] == sides[2] == side_length

        for i in range(4):
            if sides[i] + nums[index] <= side_length:
                sides[i] += nums[index]
                if dfs(index + 1):
                    return True
                sides[i] -= nums[index]

            # 如果当前边的长度为0，则不需要继续尝试其他边，因为结果会相同
            if sides[i] == 0:
                break

        return False

    return dfs(0)

解释

1. 初始化和预处理：
   • 计算总长度并判断是否可以分成四条相等的边。
   • 将火柴棍按长度从大到小排序。
2. DFS函数：
   • 递归尝试将每根火柴棍放入四条边中的一条。
   • 如果某条边的长度超过了 side_length，则回溯。
   • 如果所有火柴棍都分配完毕且四条边的长度都等于 side_length，则返回 True。
3. 剪枝优化：
   • 如果当前边的长度为0，则不需要继续尝试其他边，因为结果会相同。

通过上述步骤，我们可以有效地判断是否可以用给定的火柴棍组成一个正方形。这个问题的核心在于合理地使用回溯算法和剪枝优化，以减少不必要的搜索空间。