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拆分成两个元素和相等的子集。核心观察只有两点若totalSum sum(nums)是奇数则必然无法均分直接返回false若总和为偶数问题等价于能否选出若干元素使其子集和恰好等于totalSum / 2只要存在一个和为target的子集剩余元素自然构成另一个和为target的子集问题即告解决。这一转化是整个七种解法的共同出发点。以经典示例nums [1,5,11,5]为例总和为 22target 11存在子集[1,5,5]与[11]均和为 11因此答案为true。该示例同样出现在仓库 cpp/0416-partition-equal-subset-sum.cpp 的注释中。1. 递归Recursion——暴力搜索理解问题本质直觉在每个下标处都有两个选择把当前数字加入子集目标值相应减少跳过当前数字。递归持续削减target直到target 0→ 成功数字耗尽或target 0→ 失败。算法步骤计算totalSum sum(nums)若totalSum为奇数返回false令target totalSum // 2定义dfs(i, target)target 0→ 返回truei len(nums)或target 0→ 返回false分别尝试跳过nums[i]与取nums[i]削减 target两条分支返回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。算法步骤计算total sum(nums)奇数直接返回false令target total // 2n len(nums)创建尺寸为n × (target 1)、初始值为-1的 memo 表定义dfs(i, target)target 0→ 返回truei n或target 0→ 返回falsememo 中已有结果 → 直接返回否则计算dfs(i1, target)跳过与dfs(i1, target - nums[i])取用的或值存入 memo 并返回返回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 约束。算法步骤计算total sum(nums)奇数返回false令target total // 2n len(nums)创建尺寸(n1) × (target1)、全部初始化为false的 DP 表初始化基例对所有idp[i][0] true空集总能凑出和 0填充 DP对i从1..n对j从1..target若nums[i-1] jdp[i][j] dp[i-1][j] OR dp[i-1][j - nums[i-1]]否则dp[i][j] dp[i-1][j]返回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]取或。算法步骤计算total sum(nums)奇数返回false令target total // 2初始化两个长度为target 1的布尔数组令dp[0] true遍历每个数字num对j从1..target若j numnextDp[j] dp[j] OR dp[j - num]否则nextDp[j] dp[j]交换dp与nextDp返回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。算法步骤计算total sum(nums)奇数返回false令target total // 2初始化dp {0}和 0 恒可达逆序遍历数字顺序不影响正确性建立空集合nextDP对dp中每个和t若t num target返回true把t跳过与t num取用加入nextDP令dp nextDP循环结束仍未命中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_setint注释标明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]仍是上一轮的旧值。算法步骤计算total sum(nums)奇数返回false令target total // 2创建长度为target 1的布尔数组令dp[0] true对每个数字num令j从target递减到numdp[j] dp[j] OR dp[j - num]返回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立即提前返回trueTC 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)) ! 0C 版本使用标准库bitsetclass Solution { public: bool canPartition(vectorint nums) { int sum 0; for (int num : nums) { sum num; } if (sum % 2 ! 0) { return false; } int target sum / 2; bitset10001 dp; dp[0] 1; for (int num : nums) { dp | dp num; } return dp[target]; } };注意 C 的bitset10001意味着target上限被硬编码为 10000这契合本题输入规模约束nums长度 ≤ 200、元素值 ≤ 100最大总和 20000一半即 10000但若用于任意大输入需相应调整位宽。复杂度时间复杂度$O(n \times target)$位运算常数远小于数组版本空间复杂度$O(target)$一个整数或bitset七种解法对比总览解法思路时间复杂度空间复杂度特点1. 递归枚举取/不取$O(2^n)$$O(n)$直观仅用于理解问题2. 自顶向下 DP递归 记忆化$O(n \times target)$$O(n \times target)$保留递归语义消除重复计算3. 自底向上 DP二维表$O(n \times target)$$O(n \times target)$最标准的 0/1 背包写法4. 空间优化 DP双一维数组滚动$O(n \times target)$$O(target)$去掉行维度5. Hash Set DP可达和集合$O(n \times target)$$O(target)$实现最简洁可提前终止本仓库多语言默认解6. 最优 1D DP单数组逆序$O(n \times target)$$O(target)$面试推荐写法逆序保证 0/1 约束7. Bitset DP整数位集$O(n \times target)$$O(target)$常数因子最优依赖输入规模常见陷阱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.cppunordered_set的 Hash Set 解go/0416-partition-equal-subset-sum.go同时包含 tabulationmap 集合与基于频次统计 二分的记忆化剪枝变体javascript/0416-partition-equal-subset-sum.js同一文件内串起 DFS、记忆化、二维表、一维表四种写法适合按注释顺序逐段对比hints/partition-equal-subset-sum.md官方四步渐进式提示从奇数和直接返回到用curSum跟踪子集和并记忆化逐步引导。本题作为 0/1 背包家族的代表成员其偶数总和的必要性判断 子集和可达性 DP的分析范式可直接迁移到目标求和Target Sum、一和零Ones and Zeroes、最后一块石头的重量 IILast Stone Weight II等同类问题上值得反复推敲。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考