473. 火柴拼正方形

Difficulty
Medium
Tags
回溯
DFS
URL
https://leetcode.cn/problems/matchsticks-to-square/
Star
你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
如果你能使这个正方形，则返回 true ，否则返回 false 。
示例 1:
notion imagenotion image
输入: matchsticks = [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。
示例 2:
输入: matchsticks = [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。
提示:
  • 1 <= matchsticks.length <= 15
  • 1 <= matchsticks[i] <= 108
通过次数52,168提交次数113,019
思路
🚙
698. 划分为k个相等的子集 套娃题
题解
class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        sum_ = sum(matchsticks)
        if sum_ % 4 != 0:
            return False

        target = sum_ // 4
        self.hashset = set()
        matchsticks.sort(reverse=True)
        
        return self.helper(cur_sum=0, nums=matchsticks, start=0, target=target, k=4, used=0)

    def helper(self, cur_sum, nums, start, target, k, used):
        if k <= 0:
            return True

        if cur_sum == target:
            if used in self.hashset:
                return False
            self.hashset.add(used)
            # 开始下一个桶， 开始新桶需要从 nums[0]开始搜索
            return self.helper(cur_sum=0, 
                            nums=nums, 
                            start=0, 
                            target=target, 
                            k = k-1, 
                            used=used)

        elif cur_sum > target:
            return False

        
        for i in range(start, len(nums)):
            if used & (1 << i) != 0:
                continue

            used = used | (1 << i)
            cur_sum += nums[i]

            if self.helper(cur_sum, nums, i+1, target, k, used):
                return True
            
            used = used ^ (1 << i)
            cur_sum -= nums[i]


        return False