Python培训
400-996-5531
Python回溯法：火柴拼正方形
相信大家都听过过一个童话故事《卖火柴的小女孩》，如果以火柴为题给大家出一道python题呢？比如你现在知道小女孩有多少根火柴，那么请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。你用python代码做得到吗？
输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
示例 1:
输入：[1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。
示例 2:
输入: [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。
解决方案：
新建立一个长为4的列表存储火柴，因为这里使用的是回溯，所以火柴按由大到小的顺序存储，这样可以减少回溯可能。在火柴全部存储后，就可以判断列表中四个小列表之和是否相等，如果都相等，证明可以拼成正方形。
在写代码的时候，先判断输入数组中火柴的总和%4是否为0，这是数组里火柴能否拼成正方形的先决条件。其次，在运行代码时，新建列表中的小列表之和不可超过总和长度的1/4。利用这些条件可以使代码的时间和空间复杂度很大程度的优化。
完整代码：
def makequre(nums):
nums_sum = sum(nums)
# 数组长度小于4或者数组总和对4取余不为0
if len(nums) < 4 or nums_sum % 4 != 0:
return False
# 从大到小排序
nums = sorted(nums, reverse=True)
# 储存火柴
nums2 = [[] for i in range(4)]
return helper(0, nums, nums_sum//4, nums2)
def helper(i, nums, result, nums2):
if i >= len(nums):
return [[result] for i in range(4)]
for j in range(4):
# 每条边上存储的火柴不超过数组总和的1/4
if sum(nums2[j]) + nums[i] > result:
continue
nums2[j].append(nums[i])
if helper(i+1, nums, result, nums2):
return True
nums2[j].pop()
return False
结语
这道题虽然可以使用回溯法做出来，但这样做出来的代码的时间和空间复杂度还是比较高，特别是时间复杂度。但是回溯法的优势在于能适时“回头”，若再往前走不可能得到解，就回溯，退一步另找其他可能，这样可省去大量的无效操作。
版权声明：转载文章来自公开网络，版权归作者本人所有，推送文章除非无法确认，我们都会注明作者和来源。如果出处有误或侵犯到原作者权益，请与我们联系删除或授权事宜。
预约申请免费试听课
填写下面表单即可预约申请免费试听！ 怕学不会？助教全程陪读，随时解惑！担心就业？一地学习，可全国推荐就业！
Copyright © Tedu.cn All Rights Reserved 京ICP备08000853号-56 
京公网安备 11010802029508号 达内时代科技集团有限公司 版权所有
选择城市和中心
北京
黑龙江省
吉林省
内蒙古
河北省
陕西省
江苏省
湖北省
四川省
重庆
湖南省
江西省
贵州省
云南省
广西省
海南省
台湾