代码随想录算法训练营第三十五天|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 False
        total = sum(nums)
        if total % 2 != 0:
            return False
        target = total // 2
        dp = [0] * 10001
        for 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 True
        return 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 False
        nums.sort(reverse=True)  # 排序以便更快剪枝
        target = total // k
        if nums[0] > target:
            return False
        
        used = [False] * n
        
        def backtrack(start, current_sum, count):
            if count == k - 1:
                return True
            if 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] = True
                    if backtrack(i + 1, current_sum + nums[i], count):
                        return True
                    used[i] = False
                    # 剪枝：跳过相同数字
                    while i + 1 < n and nums[i] == nums[i + 1]:
                        i += 1
                    # 如果当前和为0，说明无法放入任何数，直接失败
                    if current_sum == 0:
                        break
            return False
        
        return 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 False
        matchsticks.sort(reverse=True)

        edges = [0] * 4
        def dfs(idx: int) -> bool:
            if idx == len(matchsticks): # 已经使用了所有火柴
                return True
            for i in range(4):
                edges[i] += matchsticks[idx] # 放入火柴
                if edges[i] <= totalLen // 4 and dfs(idx + 1):
                    return True
                edges[i] -= matchsticks[idx]
            return False
        return dfs(0)