473. 火柴拼正方形

🟠   🔖  位运算 数组 动态规划 回溯 状态压缩  🔗 力扣 LeetCode

题目

You are given an integer array matchsticks where matchsticks[i] is the length of the ith matchstick. You want to use all the matchsticks to make one square. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Return true if you can make this square and false otherwise.

Example 1:

Input: matchsticks = [1,1,2,2,2]

Output: true

Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

Example 2:

Input: matchsticks = [3,3,3,3,4]

Output: false

Explanation: You cannot find a way to form a square with all the matchsticks.

Constraints:

• 1 <= matchsticks.length <= 15
• 1 <= matchsticks[i] <= 10^8

题目大意

你将得到一个整数数组 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. 基础检查

   • 计算所有火柴的长度总和 sum，如果 sum % 4 !== 0 或者火柴数量小于 4，直接返回 false。
   • sum / 4 作为正方形的边长 sideLen。

2. 预处理

   • 降序排序：matchsticks.sort((a, b) => b - a)
     剪枝优化：尽量先放长的火柴，如果最长的火柴都无法成功填充某个边，则不需要尝试更短的火柴。

3. 回溯搜索

   • sides[i] 记录当前 4 条边的长度。
   • 遍历所有火柴，每次尝试将当前火柴放到 4 条边的某一条上：
     • 如果 sides[i] + matchsticks[x] > sideLen，说明放不下，跳过。
     • 回溯 + 递归：放置后继续尝试下一个火柴。
     • 回溯撤销：如果当前分支失败，撤回 sides[i] 的加法，尝试其他方案。

4. 剪枝优化

   • 如果某条边 sides[i] 还未填充，但和前一条边 sides[i-1] 相等，则可以跳过，减少重复搜索。

复杂度分析

• 时间复杂度：O(4^n)（最坏情况），但剪枝优化后，实际远小于指数级，在 n <= 15 以内的情况下能快速求解。
• 空间复杂度：O(n)，递归调用栈深度最多 n。

代码

var makesquare = function (matchsticks) {
	const sum = matchsticks.reduce((acc, cur) => acc + cur, 0);
	if (sum % 4 !== 0 || matchsticks.length < 4) return false;

	matchsticks.sort((a, b) => b - a); // 先排序，优先放大火柴
	const sideLen = sum / 4;
	const sides = new Array(4).fill(0);

	const backtrack = (index) => {
		if (index === matchsticks.length) {
			return sides.every((side) => side === sideLen);
		}

		for (let i = 0; i < 4; i++) {
			if (sides[i] + matchsticks[index] > sideLen) continue; // 剪枝 1: 剪掉无效选择
			if (i > 0 && sides[i] === sides[i - 1]) continue; // 剪枝 2: 避免相同状态重复搜索

			sides[i] += matchsticks[index];
			if (backtrack(index + 1)) return true;
			sides[i] -= matchsticks[index]; // 回溯
		}
		return false;
	};

	return backtrack(0);
};

相关题目

题号	标题	题解	标签	难度	力扣
2397	被列覆盖的最多行数		位运算 数组 回溯 2+	🟠	🀄️ 🔗