LeetCode 第 416 题：分割等和子集（Partition Equal Subset Sum）

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

示例：
输入：[1, 5, 11, 5]
输出：true
解释：数组可以分割为 [1, 5, 5] 和 [11]，两个子集的和均为 11。

解题思路
这个问题可以转化为：是否存在一个子集，其元素和等于整个数组元素和的一半。

1. 如果整个数组的和为奇数，直接返回 false（因为无法平分）。
2. 目标值 target = sum / 2。
3. 问题变成经典的 0-1 背包问题：从数组中选若干个数，使得它们的和恰好为 target。

第一步：暴力递归（理解核心逻辑）
尝试对每个数字选择“放入”或“不放入”子集：

• 递归函数 dfs(i, sum) 表示：考虑前 i 个数字，能否凑出和 sum。
• 递归终止条件：
  • 如果 sum == 0，返回 true（已凑出目标）。
  • 如果 i < 0 或 sum < 0，返回 false。
• 递归关系：
  • 不选第 i 个数：dfs(i-1, sum)
  • 选第 i 个数：dfs(i-1, sum - nums[i])
  • 两者任一为 true 即可。

缺点：存在大量重复计算，时间复杂度 O(2^n)。

第二步：记忆化搜索（优化递归）
用二维数组 memo[i][sum] 记录状态 (i, sum) 的结果，避免重复计算：

• 初始化 memo 为 -1（未计算）。
• 在递归中先检查 memo[i][sum]，若已计算则直接返回。
• 时间复杂度 O(n × target)，空间复杂度 O(n × target)。

第三步：动态规划（自底向上递推）
定义二维 DP 数组 dp[i][j]：前 i 个数是否能凑出和 j。

• 初始化：
  • dp[0][0] = true（不选任何数时和为 0）
  • 第一行其他位置为 false。
• 状态转移：
  • 若 j < nums[i-1]：不能选当前数，dp[i][j] = dp[i-1][j]
  • 否则：可以不选或选当前数，dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]]
• 最终答案：dp[n][target]

示例 [1,5,11,5]（target=11）的 DP 表（简化）：

数字：1,5,11,5
j=0:  [T, T, T, T, T]  // 不选任何数时和为0
i=1 (1): [T, T, F, F, F, ...] -> 可凑出0和1
i=2 (5): [T, T, F, F, F, T, T] -> 可凑出0,1,5,6
...
最终 dp[4][11] = true

第四步：动态规划空间优化
观察状态转移：dp[i][j] 只依赖于上一行 dp[i-1][...]，因此可压缩为一维数组：

• 定义 dp[j] 表示能否凑出和 j。
• 需从后向前遍历 j（避免覆盖上一轮结果）：

  for j in range(target, nums[i]-1, -1):
      dp[j] = dp[j] or dp[j - nums[i]]
  

• 初始化：dp[0] = true，其他为 false。
• 时间复杂度 O(n × target)，空间复杂度 O(target)。

最终代码（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):  # 从后往前遍历
            if dp[j - num]:
                dp[j] = True
    return dp[target]

关键点总结

1. 将问题转化为背包问题，目标为总和的一半。
2. 使用动态规划避免重复计算。
3. 空间优化时需倒序遍历，防止同一数字被重复使用。