题目

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

示例 1:

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

示例 2:

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

注意:

给定的火柴长度和在 0 到 10^9之间。
火柴数组的长度不超过15。

解题思路

和划分为k个相等的子集思路完全一样，是k = 4的特例

状态压缩dp的思路和这个完全一样的，只不过是在visited_indexs的地方用bit来表示了。

代码

class Solution:def makesquare(self, nums: List[int]) -> bool:if (not nums) or sum(nums) % 4 or max(nums) > sum(nums) // 4:return Falsevisited_indexs = [False] * len(nums)target = sum(nums) // 4def helper(nums: list, edge_cnt: int, begin_index: int, cur_sum: int) -> bool:if edge_cnt == 4:return Trueif cur_sum > target:return Falseif cur_sum == target:return helper(nums, edge_cnt + 1, 0, 0)for index in range(begin_index, len(nums)):if visited_indexs[index]:continuevisited_indexs[index] = Trueif helper(nums, edge_cnt, index + 1, cur_sum + nums[index]):return Truevisited_indexs[index] = Falsereturn Falsereturn helper(nums, 0, 0, 0)