0473. Matchsticks to Square
===========================
题目信息
--------
:题号: 0473
:难度: Medium
:主题: 火柴长度、四条等边、全部使用、不可折断
:原题: `LeetCode 0473 `_
:重点: 每根火柴恰好使用一次、不能折断、每条边可由多根组成、四条边总长度相等
题目重述
--------
给定整数数组 ``matchsticks``,每个元素表示一根火柴的长度。判断能否使用全部火柴拼成一个正方形。
每根火柴必须恰好属于正方形的一条边,不能折断,也不能剩余。每条边可以由一根或多根火柴组成,四条边的总长度必须相等且大于 0。``matchsticks.length`` 位于 ``[1, 15]``,每根长度位于 ``[1, 10^8]``。
自建示例
--------
长火柴和短火柴共同组成四边:
.. code-block:: text
输入:matchsticks = [3,3,3,3,6,6]
输出:true
解释:总长度为 24,每条边应为 6;两根长度 6 的火柴各成一边,四根长度 3 的火柴两两组成另外两边。
总长度不能被四整除:
.. code-block:: text
输入:matchsticks = [1,1,1,3]
输出:false
解释:总长度为 6,无法分成四条相等的整数长度边。
降序回溯填充四条边
------------------
正方形每条边的目标长度是总长度除以 4;若总长度不能整除或最长火柴超过目标,立即无解。将火柴按长度降序处理,尝试把当前火柴放入四条尚未超长的边中;一旦四边都达到目标,就说明所有火柴恰好被使用。
同一层回溯中,若两条边当前长度相同,把火柴放入其中任意一条的后续状态等价,可以跳过重复尝试。若一根火柴放入空边后失败,其他空边也完全对称,同样可以结束该层尝试。
C++ 实现
--------
.. code-block:: cpp
class Solution {
std::vector sticks;
std::array sides{};
int target = 0;
bool search(int index) {
if (index == static_cast(sticks.size())) return true;
int length = sticks[index];
for (int side = 0; side < 4; ++side) {
if (sides[side] + length > target) continue;
if (side > 0 && sides[side] == sides[side - 1]) continue;
sides[side] += length;
if (search(index + 1)) return true;
sides[side] -= length;
if (sides[side] == 0) break;
}
return false;
}
public:
bool makesquare(std::vector& matchsticks) {
long long total = std::accumulate(matchsticks.begin(),
matchsticks.end(), 0LL);
if (total % 4 != 0) return false;
target = static_cast(total / 4);
sticks = matchsticks;
std::sort(sticks.rbegin(), sticks.rend());
if (sticks.front() > target) return false;
sides.fill(0);
return search(0);
}
};
代码分析
--------
降序先放长火柴,能尽早暴露超出边长的分支;四条边的和始终等于已放火柴总长,递归结束时四边都不超目标就必然都等于目标。对称剪枝只删除等价状态,不会删除不同的边长分配。最坏时间复杂度为 ``O(4^n)``,额外空间复杂度为 ``O(n)``。