企业官网建设流程全解析

LeetCode 416 分割等和子集（Partition Equal Subset Sum）全解法剖析：从递归到 0/1 背包 DP 的七种进阶

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文基于本仓库的 partition-equal-subset-sum.md 配套题解展开，系统讲解 LeetCode 416「分割等和子集」从指数级递归到多项式 DP 的七种解法。读完你将掌握 0/1 背包模式的识别方法、递归 → 记忆化 → 二维 DP → 一维滚动数组 → 哈希集合 → 位集压缩的完整优化链路，并能在面试中熟练推导每种解法的时间与空间复杂度。

前置知识（Prerequisites）

在动手实现之前，建议先掌握以下四块基础：

• 动态规划（0/1 背包模式）：本题是背包问题的经典子集和（Subset Sum）变体，每个元素只能选择一次；
• 递归 + 记忆化（Memoization）：自顶向下 DP 的核心手段，用来消除重复子问题的冗余计算；
• 子集和问题：判断"是否存在一个子集，其和恰好等于给定目标值"；
• DP 空间优化：通过逆序迭代把二维 DP 压缩为一维，这是本题第 4、6 种解法的关键。

仓库中的 hints/partition-equal-subset-sum.md 给出了官方推荐的复杂度目标：应追求不差于O(n * t)时间、O(n * t)空间，其中n为数组长度，t为数组总和的一半。

问题建模：关键观察

题目要求判断能否把数组nums拆分成两个元素和相等的子集。核心观察只有两点：

1. 若totalSum = sum(nums)是奇数，则必然无法均分，直接返回false；
2. 若总和为偶数，问题等价于：

   能否选出若干元素，使其子集和恰好等于totalSum / 2？

只要存在一个和为target的子集，剩余元素自然构成另一个和为target的子集，问题即告解决。这一转化是整个七种解法的共同出发点。

以经典示例nums = [1,5,11,5]为例：总和为 22，target = 11，存在子集[1,5,5]与[11]均和为 11，因此答案为true。该示例同样出现在仓库 cpp/0416-partition-equal-subset-sum.cpp 的注释中。

1. 递归（Recursion）——暴力搜索，理解问题本质

直觉

在每个下标处都有两个选择：

1. 把当前数字加入子集（目标值相应减少）；
2. 跳过当前数字。

递归持续削减target，直到：

• target == 0→ 成功；
• 数字耗尽或target < 0→ 失败。

算法步骤

1. 计算totalSum = sum(nums)；
2. 若totalSum为奇数，返回false；
3. 令target = totalSum // 2；
4. 定义dfs(i, target)：
   • target == 0→ 返回true；
   • i == len(nums)或target < 0→ 返回false；
   • 分别尝试"跳过nums[i]"与"取nums[i]（削减 target）"两条分支；
5. 返回dfs(0, target)。

以 Python 为例：

class Solution: def canPartition(self, nums: List[int]) -> bool: if sum(nums) % 2: return False def dfs(i, target): if i >= len(nums): return target == 0 if target < 0: return False return dfs(i + 1, target) or dfs(i + 1, target - nums[i]) return dfs(0, sum(nums) // 2)

仓库 javascript/0416-partition-equal-subset-sum.js 中同样给出了基于dfs(index, subSetSum)的暴力递归实现（Time O(N^2) | Space O(N)），其剪枝逻辑与本节的边界处理完全一致。

复杂度

• 时间复杂度：$O(2^n)$
• 空间复杂度：$O(n)$（递归栈深度）

2. 动态规划（自顶向下 / 记忆化搜索）

直觉

暴力递归中存在大量重复子问题：相同的下标i+ 相同的剩余目标target会被反复计算。用一张 DP 表缓存结果即可将指数级搜索降为多项式时间：

• memo[i][t]表示"从下标i及其之后的元素中，能否凑出和t"。

算法步骤

1. 计算total = sum(nums)，奇数直接返回false；
2. 令target = total // 2，n = len(nums)；
3. 创建尺寸为n × (target + 1)、初始值为-1的 memo 表；
4. 定义dfs(i, target)：
   • target == 0→ 返回true；
   • i == n或target < 0→ 返回false；
   • memo 中已有结果 → 直接返回；
   • 否则计算dfs(i+1, target)（跳过）与dfs(i+1, target - nums[i])（取用）的或值，存入 memo 并返回；
5. 返回dfs(0, target)。

class Solution: def canPartition(self, nums: List[int]) -> bool: total = sum(nums) if total % 2 != 0: return False target = total // 2 n = len(nums) memo = [[-1] * (target + 1) for _ in range(n + 1)] def dfs(i, target): if target == 0: return True if i >= n or target < 0: return False if memo[i][target] != -1: return memo[i][target] memo[i][target] = (dfs(i + 1, target) or dfs(i + 1, target - nums[i])) return memo[i][target] return dfs(0, target)

仓库中的 go/0416-partition-equal-subset-sum.go 给出了一个更精细的记忆化变体：先对元素按值降序统计频次（countmap 与byNum排序），再用visited布尔数组缓存target层的可达状态，并通过predecessor二分查找跳过大于当前目标值的元素，是自顶向下思路的一种实战剪枝优化。

复杂度

• 时间复杂度：$O(n \times target)$
• 空间复杂度：$O(n \times target)$

其中 $n$ 为数组nums的长度，target为数组元素和的一半。

3. 动态规划（自底向上 / 二维表）

直觉

这是最经典的0/1 子集和 DP。定义：

• dp[i][j]：使用前i个数字，能否凑出和j。

对每个数字只有两个选择：

• 跳过它→ 结果继承dp[i-1][j]；
• 取用它（仅当nums[i-1] <= j）→ 检查dp[i-1][j - nums[i-1]]。

两者任一为真，dp[i][j]即为真。二维表格的每一格只依赖上一行，天然满足"每个元素只用一次"的 0/1 约束。

算法步骤

1. 计算total = sum(nums)，奇数返回false；
2. 令target = total // 2，n = len(nums)；
3. 创建尺寸(n+1) × (target+1)、全部初始化为false的 DP 表；
4. 初始化基例：对所有i，dp[i][0] = true（空集总能凑出和 0）；
5. 填充 DP：
   • 对i从1..n：
     • 对j从1..target：
       • 若nums[i-1] <= j：dp[i][j] = dp[i-1][j] OR dp[i-1][j - nums[i-1]]
       • 否则：dp[i][j] = dp[i-1][j]
6. 返回dp[n][target]。

class Solution: def canPartition(self, nums: List[int]) -> bool: total = sum(nums) if total % 2 != 0: return False target = total // 2 n = len(nums) dp = [[False] * (target + 1) for _ in range(n + 1)] for i in range(n + 1): dp[i][0] = True for i in range(1, n + 1): for j in range(1, target + 1): if nums[i - 1] <= j: dp[i][j] = (dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]) else: dp[i][j] = dp[i - 1][j] return dp[n][target]

仓库 java/0416-partition-equal-subset-sum.java 中的第一个canPartition重载正是该二维表实现（注释标明TC = O(n*sum), SC = O(n*sum)），其基例处理了i == 0与j == 0两个边界。

复杂度

• 时间复杂度：$O(n \times target)$
• 空间复杂度：$O(n \times target)$

4. 动态规划（空间优化 / 双一维数组滚动）

直觉

观察二维递推式可知，dp的当前行只依赖上一行，因此无需保留整张二维表，只需维护两个一维数组：

• dp[j]→ 处理到当前数字前，和j是否可达；
• nextDp[j]→ 处理完当前数字后，和j是否可达。

对每个数字：

• 不取→ 继承dp[j]；
• 取（可行时）→ 与dp[j - num]取或。

算法步骤

1. 计算total = sum(nums)，奇数返回false；
2. 令target = total // 2；
3. 初始化两个长度为target + 1的布尔数组，令dp[0] = true；
4. 遍历每个数字num：
   • 对j从1..target：
     • 若j >= num：nextDp[j] = dp[j] OR dp[j - num]
     • 否则：nextDp[j] = dp[j]
   • 交换dp与nextDp；
5. 返回dp[target]。

class Solution: def canPartition(self, nums: List[int]) -> bool: if sum(nums) % 2: return False target = sum(nums) // 2 dp = [False] * (target + 1) nextDp = [False] * (target + 1) dp[0] = True for i in range(len(nums)): for j in range(1, target + 1): if j >= nums[i]: nextDp[j] = dp[j] or dp[j - nums[i]] else: nextDp[j] = dp[j] dp, nextDp = nextDp, dp return dp[target]

Swift 版本（见原文档）在此处用stride(from: target, through: 1, by: -1)以逆序扫描，配合swap(&dp, &nextDp)完成滚动，与算法描述等价。

复杂度

• 时间复杂度：$O(n \times target)$
• 空间复杂度：$O(target)$

5. 动态规划（Hash Set / 可达和集合）

直觉

不用定长数组，改用哈希集合记录"当前已处理元素能凑出的所有子集和"：

• dp集合中存放所有可达和；
• 每个新数字到来时，集合中每个已有和t有两种去向：保持t（不取），或变为t + num（取）；
• 一旦某一步凑出target，即可提前终止返回true。

算法步骤

1. 计算total = sum(nums)，奇数返回false；
2. 令target = total // 2；
3. 初始化dp = {0}（和 0 恒可达）；
4. 逆序遍历数字（顺序不影响正确性）：
   • 建立空集合nextDP；
   • 对dp中每个和t：
     • 若t + num == target，返回true；
     • 把t（跳过）与t + num（取用）加入nextDP；
   • 令dp = nextDP；
5. 循环结束仍未命中target，返回false。

class Solution: def canPartition(self, nums: List[int]) -> bool: if sum(nums) % 2: return False dp = set() dp.add(0) target = sum(nums) // 2 for i in range(len(nums) - 1, -1, -1): nextDP = set() for t in dp: if (t + nums[i]) == target: return True nextDP.add(t + nums[i]) nextDP.add(t) dp = nextDP return False

这是本仓库多语言实现的默认答案：仓库 python/0416-partition-equal-subset-sum.py、cpp/0416-partition-equal-subset-sum.cpp（使用unordered_set<int>，注释标明Time: O(n x sum(nums)) / Space: O(sum(nums))）以及 go/0416-partition-equal-subset-sum.go 中的canPartitionTabulation（使用map[int]bool）均采用此策略。Go 版同样实现了"命中即返回"的提前终止优化。

复杂度

• 时间复杂度：$O(n \times target)$
• 空间复杂度：$O(target)$

6. 动态规划（最优解 / 单数组逆序迭代）

直觉

这是本问题最具代表性的最优 DP 写法：只需一个一维数组，且每个数字仅被使用一次。

• dp[j] = True表示用已处理的数字能凑出和j；
• 关键技巧：对每个数字，从target从右往左更新dp[j] = dp[j] OR dp[j - num]。

为什么必须逆序？因为正序（从左到右）更新时，dp[j - num]可能已经在本轮迭代中被当前数字更新过，等价于同一个数字被重复使用，破坏了 0/1 背包"每件物品最多取一次"的性质；逆序则保证读取的dp[j - num]仍是上一轮的旧值。

算法步骤

1. 计算total = sum(nums)，奇数返回false；
2. 令target = total // 2；
3. 创建长度为target + 1的布尔数组，令dp[0] = true；
4. 对每个数字num：
   • 令j从target递减到num：
     • dp[j] = dp[j] OR dp[j - num]
5. 返回dp[target]。

class Solution: def canPartition(self, nums: list[int]) -> bool: if sum(nums) % 2: return False target = sum(nums) // 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]

仓库中的 c/0416-partition-equal-subset-sum.c 是该解法的 C 实现（dp[j] = dp[j] || dp[j - nums[i]]，内层从targetSum递减到nums[i]），并注释说明了dp[i]的语义"是否存在一个子集其和为 i"。而 java/0416-partition-equal-subset-sum.java 的第二个canPartition重载还加入了一层小优化：仅在dp[i - no]为真时才置位dp[i]，一旦i == target立即提前返回true（TC = O(n*sum), SC = O(sum)）。

复杂度

• 时间复杂度：$O(n \times target)$
• 空间复杂度：$O(target)$

7. 动态规划（Bitset / 位集压缩）

直觉

既然dp本质是一个"下标代表和、值代表可达性"的布尔数组，那么可以把它整体压缩成一个整数位集：第j位为 1 表示和j可达。

• 初始dp = 1（只有第 0 位为 1）；
• 对每个数字num，执行dp |= dp << num——左移num位即等价于"对每个可达和加上num"；
• 最终检查第target位是否为 1。

class Solution: def canPartition(self, nums: list[int]) -> bool: total = sum(nums) if total % 2 != 0: return False target = total // 2 dp = 1 << 0 for num in nums: dp |= dp << num return (dp & (1 << target)) != 0

C++ 版本使用标准库bitset：

class Solution { public: bool canPartition(vector<int>& nums) { int sum = 0; for (int num : nums) { sum += num; } if (sum % 2 != 0) { return false; } int target = sum / 2; bitset<10001> dp; dp[0] = 1; for (int num : nums) { dp |= dp << num; } return dp[target]; } };

注意 C++ 的bitset<10001>意味着target上限被硬编码为 10000，这契合本题输入规模约束（nums长度 ≤ 200、元素值 ≤ 100，最大总和 20000，一半即 10000），但若用于任意大输入需相应调整位宽。

复杂度

• 时间复杂度：$O(n \times target)$（位运算常数远小于数组版本）
• 空间复杂度：$O(target)$（一个整数或bitset）

七种解法对比总览

常见陷阱（Common Pitfalls）

陷阱一：忘记奇数和的检查

最常见的错误是在开始 DP 之前没有检查sum(nums)是否为奇数。若总和为奇数，两个等和子集不可能存在，必须立即返回false。漏掉该检查要么得到错误结果，要么白白浪费大量计算。

陷阱二：一维 DP 使用从左到右的正序迭代

使用一维 DP 数组时，从左到右迭代会让同一个元素在本轮中被重复计入，破坏 0/1 背包性质。必须从右到左（target递减到num）迭代，确保每个元素在每个子集中至多被使用一次。这正是第 6 种解法正确性的核心，也是面试官最常追问的细节。

陷阱三：目标值计算中的整数溢出

在不支持任意精度整数的语言（如 Java、C++ 的int）中，先求和再除以 2 的流程可能发生溢出。求totalSum时应使用足够宽的数据类型（如 Java/C++ 的long），再除以 2 得到target，避免溢出导致错误结果。

扩展：仓库源码研读指引

若想进一步对照学习，可在本仓库中阅读以下实现：

• python/0416-partition-equal-subset-sum.py：默认 Hash Set 解，含提前终止；
• java/0416-partition-equal-subset-sum.java：同时给出二维表与一维逆序两个版本，带复杂度注释；
• c/0416-partition-equal-subset-sum.c：一维逆序的简洁 C 实现；
• cpp/0416-partition-equal-subset-sum.cpp：unordered_set的 Hash Set 解；
• go/0416-partition-equal-subset-sum.go：同时包含 tabulation（map 集合）与基于频次统计 + 二分的记忆化剪枝变体；
• javascript/0416-partition-equal-subset-sum.js：同一文件内串起 DFS、记忆化、二维表、一维表四种写法，适合按注释顺序逐段对比；
• hints/partition-equal-subset-sum.md：官方四步渐进式提示，从"奇数和直接返回"到"用curSum跟踪子集和并记忆化"逐步引导。

本题作为 0/1 背包家族的代表成员，其"偶数总和的必要性判断 + 子集和可达性 DP"的分析范式，可直接迁移到目标求和（Target Sum）、一和零（Ones and Zeroes）、最后一块石头的重量 II（Last Stone Weight II）等同类问题上，值得反复推敲。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode