代码随想录算法训练营第三十五天|416. 分割等和子集、698.划分为k个相等的子集、473.火柴拼正方形

416. 分割等和子集

题目链接：416. 分割等和子集 - 力扣（LeetCode）

思考：本题要将数组分为两个子数组，且两个子数组和相等，因此首先可以想到的条件就是数组可分为两个，这要求数组元素数量>1，要想两个子数组和相等，则原始数组和为偶数才行。

处理完上述特殊条件后，需要考虑如何划分数组。由于要把原始数组划分为两个子数组且两个数组和相等，则每个数组元素和为原始数组总和的一半。令这个总和的一半为target，则需要在原始数组中找到是否存在某个元素等于target，或是存在几个元素之和为target。

这里要注意的是，本题与在某个数组中寻找是否存在元素target不一样，因为本题的target不一定是一个元素，可以是多个元素之和，具体是几个元素之和不确定。因此本题想要直接暴力求解的话，会特别耗时。

因此需要结合01背包思想解决问题，将寻找元素和为target的问题转化为容量为target的背包，恰好需要装满的问题。把所有元素当做可以装入背包的物品，每个元素占用空间和带来的价值都是元素数值本身。

初始化dp全0数组，下标表示背包容量，下标对应的数组值表示背包可以装入物品的最大重量。本题难点在于循环条件和递推公式，首先要遍历所有物品，然后依据背包容量，更新背包装入的物品重量，即：

• 外层循环：遍历每个数字 num。

• 内层循环：从 target 逆向遍历到 num（避免重复计算）。

  • 状态转移：对于容量 j，选择是否装入 num：

    • 不装：dp[j] 保持不变。

    • 装：dp[j-num] + num（当前和加上 num 的值）。

  • 取两者最大值更新 dp[j]。

代码：

class Solution:def canPartition(self, nums: List[int]) -> bool:n = len(nums)if n <= 1:return Falsetotal = sum(nums)if total % 2 != 0:return Falsetarget = total // 2dp = [0] * 10001for num in nums:for j in range(target, num-1, -1):dp[j] = max(dp[j], dp[j-num]+num)if dp[target] == target:return Truereturn False

698.划分为k个相等的子集

题目链接：698. 划分为k个相等的子集 - 力扣（LeetCode）

思考：要判断是否可以将数组分成k个非空子集，且每个子集的和相等，可以按照以下步骤进行：

1. 总和检查：首先计算数组所有元素的总和。如果总和不能被k整除，直接返回False，因为无法均分。

2. 目标子集和：计算每个子集的目标和，即总和除以k。

3. 排序优化：将数组排序，先处理较大的数，可以更快地剪枝无效路径。

4. 回溯法：使用回溯法尝试将数字分配到各个子集中。每次尝试将当前数字放入一个子集，如果该子集的和不超过目标和，则继续递归处理剩下的数字。如果所有数字都能成功分配，则返回True，否则回溯并尝试其他可能性。

代码：

class Solution:def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:n = len(nums)total = sum(nums)if total % k != 0:return Falsenums.sort(reverse=True)  # 排序以便更快剪枝target = total // kif nums[0] > target:return Falseused = [False] * ndef backtrack(start, current_sum, count):if count == k - 1:return Trueif current_sum == target:return backtrack(0, 0, count + 1)for i in range(start, n):if not used[i] and current_sum + nums[i] <= target:used[i] = Trueif backtrack(i + 1, current_sum + nums[i], count):return Trueused[i] = False# 剪枝：跳过相同数字while i + 1 < n and nums[i] == nums[i + 1]:i += 1# 如果当前和为0，说明无法放入任何数，直接失败if current_sum == 0:breakreturn Falsereturn backtrack(0, 0, 0)

473.火柴拼正方形

题目链接：473. 火柴拼正方形 - 力扣（LeetCode）

思考：首先计算所有火柴的总长度 totalLen，如果 totalLen 不是 4 的倍数，那么不可能拼成正方形，返回 false。当 totalLen 是 4 的倍数时，每条边的边长为 len= totalLen/4，用 edges 来记录 4 条边已经放入的火柴总长度。对于第 index 火柴，尝试把它放入其中一条边内且满足放入后该边的火柴总长度不超过 len，然后继续枚举第 index+1 根火柴的放置情况，如果所有火柴都已经被放置，那么说明可以拼成正方形。

为了减少搜索量，需要对火柴长度从大到小进行排序。

代码：

class Solution:def makesquare(self, matchsticks: List[int]) -> bool:totalLen = sum(matchsticks)if totalLen % 4:return Falsematchsticks.sort(reverse=True)edges = [0] * 4def dfs(idx: int) -> bool:if idx == len(matchsticks): # 已经使用了所有火柴return Truefor i in range(4):edges[i] += matchsticks[idx] # 放入火柴if edges[i] <= totalLen // 4 and dfs(idx + 1):return Trueedges[i] -= matchsticks[idx]return Falsereturn dfs(0)