我来给你讲解 LeetCode 第 416 题「分割等和子集」。

题目描述

给定一个只包含正整数的非空数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11]。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

问题分析

第一步：理解问题本质

题目要求将数组分成两个和相等的子集。这意味着：

• 两个子集的和都等于整个数组和的一半
• 设数组总和为 sum，那么每个子集的和应该是 sum/2

关键观察：

1. 如果 sum 是奇数，直接返回 false（因为无法平分）
2. 问题转化为：能否从数组中选出一些数，使它们的和等于 sum/2

第二步：转化为背包问题

这实际上是一个 0-1 背包问题：

• 背包容量：target = sum/2
• 物品：数组中的每个数字
• 物品重量：数字的值
• 物品价值：数字的值
• 问题：能否恰好装满容量为 target 的背包？

解题思路

方法一：动态规划

定义 dp[i][j] 表示：考虑前 i 个物品，能否恰好装满容量为 j 的背包。

状态转移方程：

• 如果不选第 i 个物品：dp[i][j] = dp[i-1][j]
• 如果选第 i 个物品：dp[i][j] = dp[i-1][j - nums[i]]
• 综合：dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i]]

边界条件：

• dp[0][0] = true（容量为0时，不选任何物品即可）
• dp[i][0] = true（容量为0时，总是可以装满）
• dp[0][j] = false（j > 0，没有物品可用）

方法二：空间优化

由于 dp[i] 只依赖于 dp[i-1]，可以优化为一维数组：

dp[j] = dp[j] || dp[j - nums[i]]

注意： 需要从后往前遍历，避免重复计算。

详细解题步骤

步骤1：计算总和并检查基本情况

def canPartition(nums):
    total_sum = sum(nums)
    
    # 如果总和是奇数，直接返回false
    if total_sum % 2 != 0:
        return False
    
    target = total_sum // 2

步骤2：特殊情况处理

    # 如果最大数大于目标值，直接返回false
    if max(nums) > target:
        return False
    
    # 如果最大数等于目标值，直接返回true
    if max(nums) == target:
        return True

步骤3：动态规划实现

    # 初始化dp数组
    dp = [False] * (target + 1)
    dp[0] = True  # 容量为0时总是可以装满
    
    # 遍历每个数字
    for num in nums:
        # 从后往前遍历，避免重复使用同一个数字
        for j in range(target, num - 1, -1):
            if dp[j - num]:  # 如果j-num可以达到，那么选择当前数字后j也可以达到
                dp[j] = True
    
    return dp[target]

完整示例演示

以 nums = [1, 5, 11, 5] 为例：

1. 计算总和：1 + 5 + 11 + 5 = 22（偶数）
2. 目标值：target = 11
3. 初始化dp：dp = [True, False, False, ..., False]（长度12）

遍历过程：

• 数字1：dp[1] = True
• 数字5：dp[5] = True, dp[6] = True
• 数字11：dp[11] = True（因为dp[0]为True）
• 返回 dp[11] = True

复杂度分析

• 时间复杂度：O(n × target)，其中 n 是数组长度
• 空间复杂度：O(target)

关键点总结

1. 问题转化：将分割问题转化为子集和问题
2. 背包思想：使用0-1背包的动态规划思路
3. 空间优化：从二维压缩到一维，注意遍历顺序
4. 剪枝优化：提前处理特殊情况提高效率

这个解法既高效又易于理解，是解决这类问题的标准方法。