LeetCode 473. 火柴拼正方形

字数 2009 2025-12-15 05:17:47

LeetCode 473. 火柴拼正方形

题目描述

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

如果你能拼出正方形，则返回 true，否则返回 false。

示例 1:

输入: matchsticks = [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为 2 的正方形，每边用两根火柴（1+1, 2）。

示例 2:

输入: matchsticks = [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。

解题过程

这个问题可以被视为一个深度优先搜索（DFS） 或回溯问题，其核心是将一组数字（火柴）分配到四个“桶”（正方形的四条边）中，使得每个桶内的数字总和都等于一个目标值（边长）。

第一步：初步判断与预处理

计算总长度：首先，计算所有火柴的总和 total。如果 total 不能被 4 整除，那么绝对不可能拼成一个正方形，直接返回 false。
计算目标边长：正方形的边长 side 等于 total / 4。
排序优化：对火柴数组进行降序排序。这是一个关键的优化步骤。在尝试将火柴放入边的过程中，先尝试用掉较长的火柴，可以更早地触发“和超过目标边长”的剪枝条件，从而减少无效的搜索分支，提高效率。

第二步：核心思路与状态定义

我们把问题想象成有四个空的“边”（sides[0], sides[1], sides[2], sides[3]），初始时每个边的当前和为 0。

我们需要遍历每一根火柴，尝试将它放入四条边中的一条。放置规则是：

放入后，该边的当前和不能超过目标边长 side。
每根火柴必须被放入一次且仅一次。

如果所有火柴都能被成功放入，并且最终四条边的和都恰好等于 side，则成功。

状态定义：

sides[4]：一个长度为 4 的数组，记录当前四条边的当前长度和。
index：当前正在尝试放置第 index 根火柴（排序后的）。

第三步：深度优先搜索（DFS）函数设计

我们将实现一个递归函数 dfs(index)，表示尝试放置第 index 根火柴。

递归函数的流程：

基准情况：如果 index 等于火柴总数，意味着所有火柴都已尝试放置。此时检查 sides 数组是否四条边都等于 side。如果是，返回 true；否则返回 false。
遍历四条边：对于当前火柴 matchsticks[index]，我们尝试将它放入第 i 条边（i 从 0 到 3）。
剪枝条件：
- 可行性剪枝：如果 sides[i] + matchsticks[index] > side，说明放入这根火柴会导致这条边的长度超过目标边长，这是不允许的，跳过当前边，尝试下一条。
- 去重剪枝：如果 sides[i] 的当前值，与 sides[i-1] 的当前值相等，并且我们跳过前一条边 i-1 是因为它放不下当前火柴（本质上是由于放不下的条件相同，导致两条边在当前状态下是“等效”的），那么当前边 i 的尝试是多余的，可以跳过，避免重复搜索。这是优化搜索空间的关键。
选择：如果通过剪枝条件，将当前火柴的长度加到 sides[i] 上。
递归：递归调用 dfs(index + 1)，尝试放置下一根火柴。
回溯：如果从递归调用返回的结果是 false，说明当前这个放置选择最终无法成功。我们需要“撤销”这个选择，将当前火柴的长度从 sides[i] 中减去，然后尝试将火柴放入下一条边。
返回结果：如果在遍历四条边的尝试中，有任何一条边能引导至成功（递归返回 true），则整个函数返回 true。如果所有尝试都失败，返回 false。

第四步：算法步骤总结

计算总和 total 和目标边长 side。如果 total % 4 != 0，返回 false。
对 matchsticks 数组进行降序排序。
初始化一个长度为 4 的数组 sides，所有元素为 0。
调用并返回 dfs(0) 的结果。

第五步：复杂度分析

时间复杂度：最坏情况下是 O(4^N)，其中 N 是火柴数量。但通过排序、可行性剪枝和去重剪枝，实际运行效率在 LeetCode 测试用例上是可以接受的。
空间复杂度：O(N)，主要用于递归调用栈的深度（最大为 N 层）。

核心要点回顾：

问题转换：将“拼正方形”问题转化为“等和四子集划分”问题。
预处理：总和整除性检查和降序排序是重要的优化起点。
DFS+回溯：核心是尝试将每根火柴分配到四个“桶”中的一个。
关键剪枝：
- 可行性剪枝：保证单边和不超过目标值。
- 去重剪枝：当多条边在当前状态下长度相同时，避免重复搜索相同的分配模式，这是算法效率的核心优化点之一。

LeetCode 473. 火柴拼正方形题目描述你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 根火柴的长度。你需要用所有的火柴拼成一个正方形。你不能折断任何一根火柴，但可以把它们连接起来，并且每根火柴必须恰好使用一次。如果你能拼出正方形，则返回 true ，否则返回 false 。示例 1: 示例 2: 解题过程这个问题可以被视为一个深度优先搜索（DFS）或回溯问题，其核心是将一组数字（火柴）分配到四个“桶”（正方形的四条边）中，使得每个桶内的数字总和都等于一个目标值（边长）。第一步：初步判断与预处理计算总长度：首先，计算所有火柴的总和 total 。如果 total 不能被 4 整除，那么绝对不可能拼成一个正方形，直接返回 false 。计算目标边长：正方形的边长 side 等于 total / 4 。排序优化：对火柴数组进行降序排序。这是一个关键的优化步骤。在尝试将火柴放入边的过程中，先尝试用掉较长的火柴，可以更早地触发“和超过目标边长”的剪枝条件，从而减少无效的搜索分支，提高效率。第二步：核心思路与状态定义我们把问题想象成有四个空的“边”（ sides[0] , sides[1] , sides[2] , sides[3] ），初始时每个边的当前和为 0。我们需要遍历每一根火柴，尝试将它放入四条边中的一条。放置规则是：放入后，该边的当前和不能超过目标边长 side 。每根火柴必须被放入一次且仅一次。如果所有火柴都能被成功放入，并且最终四条边的和都恰好等于 side ，则成功。状态定义： sides[4] ：一个长度为 4 的数组，记录当前四条边的当前长度和。 index ：当前正在尝试放置第 index 根火柴（排序后的）。第三步：深度优先搜索（DFS）函数设计我们将实现一个递归函数 dfs(index) ，表示尝试放置第 index 根火柴。递归函数的流程：基准情况：如果 index 等于火柴总数，意味着所有火柴都已尝试放置。此时检查 sides 数组是否四条边都等于 side 。如果是，返回 true ；否则返回 false 。遍历四条边：对于当前火柴 matchsticks[index] ，我们尝试将它放入第 i 条边（ i 从 0 到 3）。剪枝条件：可行性剪枝：如果 sides[i] + matchsticks[index] > side ，说明放入这根火柴会导致这条边的长度超过目标边长，这是不允许的，跳过当前边，尝试下一条。去重剪枝：如果 sides[i] 的当前值，与 sides[i-1] 的当前值相等，并且我们跳过前一条边 i-1 是因为它放不下当前火柴（本质上是由于放不下的条件相同，导致两条边在当前状态下是“等效”的），那么当前边 i 的尝试是多余的，可以跳过，避免重复搜索。这是优化搜索空间的关键。选择：如果通过剪枝条件，将当前火柴的长度加到 sides[i] 上。递归：递归调用 dfs(index + 1) ，尝试放置下一根火柴。回溯：如果从递归调用返回的结果是 false ，说明当前这个放置选择最终无法成功。我们需要“撤销”这个选择，将当前火柴的长度从 sides[i] 中减去，然后尝试将火柴放入下一条边。返回结果：如果在遍历四条边的尝试中，有任何一条边能引导至成功（递归返回 true ），则整个函数返回 true 。如果所有尝试都失败，返回 false 。第四步：算法步骤总结计算总和 total 和目标边长 side 。如果 total % 4 != 0 ，返回 false 。对 matchsticks 数组进行降序排序。初始化一个长度为 4 的数组 sides ，所有元素为 0。调用并返回 dfs(0) 的结果。第五步：复杂度分析时间复杂度：最坏情况下是 O(4^N)，其中 N 是火柴数量。但通过排序、可行性剪枝和去重剪枝，实际运行效率在 LeetCode 测试用例上是可以接受的。空间复杂度：O(N)，主要用于递归调用栈的深度（最大为 N 层）。核心要点回顾：问题转换：将“拼正方形”问题转化为“等和四子集划分”问题。预处理：总和整除性检查和降序排序是重要的优化起点。 DFS+回溯：核心是尝试将每根火柴分配到四个“桶”中的一个。关键剪枝：可行性剪枝：保证单边和不超过目标值。去重剪枝：当多条边在当前状态下长度相同时，避免重复搜索相同的分配模式，这是算法效率的核心优化点之一。