Leetcode【473、698】
Leetcode【473、698】
问题描述：【Greedy+DFS】473. Matchsticks to Square
解题思路：
火柴拼正方形。给一个表示火柴长度的数组，判断是否可以拼成一个正方形。
分析一下题意，其实这道题是在问：能不能把一组数字分成 4 组，每组的和是相同的。
因此，这道题和下面的 Leetcode 698 几乎相同，Leetcode 698 是划分成 k 组，而这道题是划分成 4 组，因此我们把 Leetcode 698 的代码中 k 改成 4 就是这道题的答案。注意这道题 0 <= 数组长度 <= 15，因此还要加上数组为空的判断即可。
但是，按照 Leetcode 698 中两个方法，方法 1 超时了，方法 2 可以通过，而且快很多（beats 73%），玄学。
Python3 实现：
class Solution:
def makesquare(self, nums: List[int]) -> bool:
def search(ind): # ind为nums下标，从0开始
if ind == N: # 将nums全部数填入targets，返回True
return True
for i in range(4): # 对于每一个targets
if targets[i] >= nums[ind]: # 保证targets该位置的数字>=放置的数字
targets[i] -= nums[ind]
if search(ind + 1):
return True
targets[i] += nums[ind] # 回溯
return False
div, mod = divmod(sum(nums), 4)
if mod != 0:
return False
nums.sort(reverse=True) # 降序排序可以减少递归次数(亲测)
if not nums or nums[0] > div: # 数组可能为空
return False
N = len(nums)
targets = [div] * 4 # 4个大小为目标数的桶
return search(0)问题描述：【Greedy+DFS】698. Partition to K Equal Sum Subsets
解题思路：
划分成 k 个相等的子集和。给一个数组和 k，将数组划分成 k 个子集，使得每个子集和相等。如果可以划分，返回True，否则返回 False。
首先，根据题意可以做一些初步的判断：
- 对所有数求和，再除以 k，如果余数不为 0，说明不可能划分，直接返回 False；否则，商就是每个子集的目标数；
- 对数组进行从大到小排序，如果数组第一个数大于目标数，说明不可能划分，直接返回 False。
方法1（80ms）：
因为数组大小 <= 16，因此可以用 DFS 回溯法求解。每当找到一组划分，就将 k 减 1，并且恢复原始目标值继续判断；如果 k 变为 0，说明可以划分成 k 个子集，返回 True。
注意：前面对数组从大到小排序在回溯过程中也是非常有必要的，因为这样做保证了大的数字先进行组合成目标数，可以减少迭代次数（贪心思想）。
时间复杂度为 O(N!)。
Python3 实现：
class Solution:
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
def search(k, target):
if target == 0: # 找到一组划分，k减1
k -= 1
target = div # 将原目标值div重新赋给target
if k == 0:
return True
for i in range(N): # 对于数组中的每一个数
if not b[i] and target >= nums[i]: # 剪枝
b[i] = True
if search(k, target-nums[i]):
return True
b[i] = False # 回溯
return False
div, mod = divmod(sum(nums), k)
if mod != 0:
return False
nums.sort(reverse=True) # 降序排序可以减少递归次数(亲测)
if nums[0] > div:
return False
N = len(nums)
b = [False] * N # 标记数是否被使用
return search(k, div)方法2（1480ms）：
其实，这道题还有另外一种 DFS 回溯方法，就是构造大小为 k 的数组 targets，初始值为每个子集的目标数。这里可以理解为构造了 k 个大小为目标数的“桶”。然后，在回溯过程中，我们将数组中的每个数递归放入到这 k 个“桶”中（回溯函数参数就是数组的索引）。如果所有数都能放到“桶”中（数组索引达到数组长度），说明可以划分成 k 个相等的子集，返回 True。
证明：为什么只需要判断恰好用完即可返回 True？ 因为 sum(targets) = div * k = sum(nums)。如果在 targets 的每个位置放数字的时候，保证了 targets 该位置的数字 >= 放置的数字，即保证了在最终状态的 targets[i] >= 0。此时有 sum(target) >= 0。又已知所有数字恰好用完，所以恰好有 sum(target) = 0。故，当所有数字恰好用完时，targets 数组中每个位置都是 0。
同样的，编程时要对数组进行从大到小排序，可以保证大的数先组合成目标数（大的数先放入“桶”中，贪心思想）。这种方法的时间复杂度和上述方法一样，均是 O(N!)，但是速度要慢一些（可能迭代的次数多一些吧）。
Python3 实现：
class Solution:
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
def search(ind): # ind为nums下标，从0开始
if ind == N: # 将nums全部数填入targets，返回True
return True
for i in range(k): # 对于每一个targets
if targets[i] >= nums[ind]: # 保证targets该位置的数字>=放置的数字
targets[i] -= nums[ind]
if search(ind + 1):
return True
targets[i] += nums[ind] # 回溯
return False
div, mod = divmod(sum(nums), k)
if mod != 0:
return False
nums.sort(reverse=True) # 降序排序可以减少递归次数(亲测)
if nums[0] > div:
return False
N = len(nums)
targets = [div] * k # k个大小为目标数的桶
return search(0)