本文共 1227 字，大约阅读时间需要 4 分钟。
目标是将一堆火柴棒拼成一个正方形。每个边必须由相同数量的火柴棒组成，且四个边的火柴数量必须相等。例如，一个边由4根火柴组成，那么正方形需要4×4=16根火柴。
我们可以使用深度优先搜索（DFS）结合剪枝优化来解决这个问题。剪枝优化是为了减少不必要的搜索路径，提高算法效率。
class Solution: def makesquare(self, nums: List[int]) -> bool: if not nums: return False total = sum(nums) each = total >> 2 if (each << 2) != total: return False nums.sort(reverse=True) square = [0] * 4 def dfs(index): if index == len(nums): return square[0] == square[1] == square[2] == square[3] for i in range(4): if square[i] + nums[index] <= each: square[i] += nums[index] if dfs(index + 1): return True square[i] -= nums[index] return False return dfs(0)
O(n^4)
O(n)
排序数组：将数组从大到小排序。这样可以先尝试放大火柴棒，减少不必要的尝试，提前终止错误的方案。
剪枝条件：在尝试放入火柴棒时，如果当前火柴棒的数量已经超过了每边的最大值（each），则直接终止该路径。
回溯：使用深度优先搜索，尝试将火柴棒放入四个边中的一个，当某一边的火柴棒数量超过each时，回退并尝试其他边。
each。each。each，立即回退，避免不必要的搜索。通过这种方法，我们可以高效地解决火柴棒拼正方形的问题，同时保证算法的正确性和效率。
转载地址：http://whba.baihongyu.com/