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

题目描述

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

示例 1
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11]，它们的和都是 11。

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

第一步：问题转化

如果数组总和是奇数，那么不可能分成两个和相等的子集（因为和相等意味着每个子集的和 = 总和 / 2，总和为奇数时无法整除）。
所以第一步：

1. 计算 sum(nums)。
2. 如果 sum(nums) 是奇数，直接返回 false。
3. 如果 sum(nums) 是偶数，设 target = sum(nums) // 2。

问题转化为：能否从数组 nums 中选出一些数，使它们的和等于 target。
这是一个典型的 0-1 背包问题。

第二步：动态规划思路

定义 dp[i][j] 表示：考虑前 i 个数字（索引 0 到 i-1），能否选出一些数使得它们的和等于 j。

• 如果 j == 0，不选任何数即可，所以 dp[i][0] = true。
• 如果 i == 0 且 j > 0，没有数字可选，dp[0][j] = false（除了 j=0）。

状态转移：

1. 如果 j < nums[i-1]，那么不能选第 i 个数字，所以 dp[i][j] = dp[i-1][j]。
2. 如果 j >= nums[i-1]，有两种选择：
   • 不选第 i 个数字：dp[i][j] = dp[i-1][j]
   • 选第 i 个数字：dp[i][j] = dp[i-1][j - nums[i-1]]
     两者取“或”运算（只要有一种成立即可）。

最终答案：dp[n][target]，其中 n = len(nums)。

第三步：空间优化

观察状态转移方程，dp[i][j] 只依赖于 dp[i-1][...]，所以可以优化为一维数组 dp[j] 表示：能否凑出和 j。

遍历顺序：

• 外层循环遍历每个数字 num。
• 内层循环遍历 j 从 target 到 num（倒序遍历，避免同一数字被重复使用）。

初始化：dp[0] = true（和为 0 总是可以做到），其余为 false。

第四步：详细步骤演示

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

• 总和 = 22，target = 11。
• 初始化 dp = [True] + [False] * 11。

遍历过程：

1. num = 1
   j 从 11 到 1：
   j=11: dp[11] = dp[11] or dp[10] = False or False = False
   j=10: dp[10] = dp[10] or dp[9] = False or False = False
   ...
   j=1: dp[1] = dp[1] or dp[0] = False or True = True
   此时 dp = [T, T, F, F, F, F, F, F, F, F, F, F]

2. num = 5
   j 从 11 到 5：
   j=11: dp[11] = dp[11] or dp[6] = False or False = False
   j=10: dp[10] = dp[10] or dp[5] = False or False = False
   j=9: dp[9] = dp[9] or dp[4] = False or False = False
   j=8: dp[8] = dp[8] or dp[3] = False or False = False
   j=7: dp[7] = dp[7] or dp[2] = False or False = False
   j=6: dp[6] = dp[6] or dp[1] = False or True = True
   j=5: dp[5] = dp[5] or dp[0] = False or True = True
   此时 dp = [T, T, F, F, F, T, T, F, F, F, F, F]

3. num = 11
   j 从 11 到 11：
   j=11: dp[11] = dp[11] or dp[0] = False or True = True
   此时 dp[11] 已为 True，提前结束也可。

4. 最终 dp[11] = True，返回 true。

第五步：代码实现（Python）

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
    return dp[target]

第六步：复杂度分析

• 时间复杂度：O(n × target)，n 为数组长度，target 为总和的一半。
• 空间复杂度：O(target)。

这个题目通过转化为 0-1 背包问题，并用动态规划求解，是面试中常见的题型。