题目描述
你将得到一个整数数组 matchsticks ,其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒,但你可以把它们连在一起,而且每根火柴棒必须 使用一次 。
如果你能使这个正方形,则返回 true ,否则返回 false 。
样例
示例1
输入: matchsticks = [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形,每边两根火柴。
示例2
输入: matchsticks = [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。
DFS + 剪枝
1.从大到小枚举所有边
2.每条边内部的木棒长度规定成从大到小
3.如果当前木棒拼接失败,则跳过接下来所有长度相同的木棒
4.如果当前木棒拼接失败,且是当前边的第一个,则直接剪掉当前分
5.如果当前木棒拼接失败,且是当前边的最后一个,则直接剪掉当前分支
C++ 代码
class Solution {
public:
vector<bool> st;
bool makesquare(vector<int>& matchsticks) {
int num = 0;
for (auto t : matchsticks) num += t;
if(!num || num % 4) return false;
st = vector<bool>(matchsticks.size());
sort(matchsticks.begin(), matchsticks.end(), greater<int>());
return dfs(matchsticks, 0, 0, num / 4);
}
bool dfs(vector<int>& nums, int u, int cur, int length)
{
if (cur == length) u ++, cur = 0;
if (u == 4) return true;
for (int i = 0; i < nums.size(); i ++)
{
if (!st[i] && nums[i] + cur <= length)
{
st[i] = true;
if (dfs(nums, u, cur + nums[i], length)) return true;
st[i] = false;
if (!cur) return false;
if (cur + nums[i] == length) return false;
while (i + 1 < nums.size() && nums[i + 1] == nums[i]) i ++;
}
}
return false;
}
};