荆门市网站建设_网站建设公司_SEO优化_seo优化

Java版LeetCode热题100之分割等和子集：从NP完全问题到0-1背包的深度解析

本文全面剖析 LeetCode 第416题「分割等和子集」，这是一道经典的 NP 完全问题，可转化为 0-1 背包模型。文章涵盖题目理解、动态规划建模、二维与一维DP实现、复杂度分析、面试高频问题、实际应用场景及延伸思考，是一篇面向中高级开发者的高质量技术博客。

一、原题回顾

题目编号：LeetCode 416
题目名称：分割等和子集（Partition Equal Subset Sum）
难度等级：中等（Medium）

题目描述

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

注意：子集不要求连续，但每个元素只能使用一次。

示例

示例 1： 输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11]，两者和均为 11。 示例 2： 输入：nums = [1,2,3,5] 输出：false 解释：总和为 11，无法分成两个和为 5.5 的子集（必须为整数）。

约束条件

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

二、原题分析

2.1 问题本质：NP 完全问题

本题是著名的Partition Problem（划分问题），属于NP 完全问题。这意味着：

• 目前没有已知的多项式时间算法（如 O(n²)、O(n log n)）；
• 若你能找到一个多项式解法，就证明了P = NP，可获图灵奖！

因此，我们必须接受伪多项式时间复杂度的解法——即时间复杂度与输入数值大小相关，而非仅与输入长度相关。

2.2 关键转化：0-1 背包问题

观察题目要求：

• 将数组分为两个子集，和相等；
• 等价于：是否存在一个子集，其和等于总和的一半。

设总和为sum，则目标为target = sum / 2。

于是问题转化为：

能否从数组中选出若干元素（每个最多选一次），使其和恰好等于target？

这正是0-1 背包问题的判定版本！

• “物品”：数组中的每个数字；
• “重量” = “价值” = 数字本身；
• “背包容量” =target；
• 问：能否装满背包？

2.3 预处理剪枝

在正式 DP 前，可进行以下快速判断：

1. 数组长度 < 2→ 无法分割，返回false；
2. 总和为奇数→ 无法均分，返回false；
3. 最大元素 > target→ 该元素无法放入任何子集而不超限，返回false。

这些剪枝能显著提升效率，尤其在边界 case 中。

三、答案构思：方法一 —— 二维动态规划

3.1 状态定义

定义dp[i][j]表示：

从前i+1个元素（即nums[0..i]）中，能否选出若干元素，使其和恰好为j。

• i范围：0到n-1
• j范围：0到target

3.2 状态转移方程

对于每个元素nums[i]，有两种选择：

1. 不选：则dp[i][j] = dp[i-1][j]
2. 选（仅当j >= nums[i]）：则dp[i][j] = dp[i-1][j - nums[i]]

只要有一种选择可行，dp[i][j]即为true：

d p [ i ] [ j ] = { d p [ i − 1 ] [ j ] ∨ d p [ i − 1 ] [ j − n u m s [ i ] ] , if j ≥ n u m s [ i ] d p [ i − 1 ] [ j ] , otherwise dp[i][j] = \begin{cases} dp[i-1][j] \lor dp[i-1][j - nums[i]], & \text{if } j \geq nums[i] \\ dp[i-1][j], & \text{otherwise} \end{cases}dp[i][j]={dp[i−1][j]∨dp[i−1][j−nums[i]],dp[i−1][j],​ifj≥nums[i]otherwise​

3.3 边界条件

• 和为 0：不选任何元素即可，故对所有i，dp[i][0] = true
• 第一个元素：dp[0][nums[0]] = true

3.4 最终答案

dp[n-1][target]即为所求。

四、完整答案（方法一：二维DP）

publicclassSolution{publicbooleancanPartition(int[]nums){intn=nums.length;if(n<2)returnfalse;intsum=0,maxNum=0;for(intnum:nums){sum+=num;maxNum=Math.max(maxNum,num);}// 剪枝1：总和为奇数if(sum%2!=0)returnfalse;inttarget=sum/2;// 剪枝2：最大元素超过 targetif(maxNum>target)returnfalse;// dp[i][j]: 前 i+1 个元素能否组成和 jboolean[][]dp=newboolean[n][target+1];// 初始化：和为0总是可行for(inti=0;i<n;i++){dp[i][0]=true;}// 第一个元素dp[0][nums[0]]=true;// 填表for(inti=1;i<n;i++){intnum=nums[i];for(intj=1;j<=target;j++){if(j>=num){dp[i][j]=dp[i-1][j]||dp[i-1][j-num];}else{dp[i][j]=dp[i-1][j];}}}returndp[n-1][target];}}

代码说明

• 先进行必要剪枝；
• 显式初始化边界；
• 双重循环填表，逻辑清晰；
• 返回最终状态。

五、代码分析（方法一）

5.1 正确性验证

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

• sum = 22,target = 11
• maxNum = 11 <= 11，继续

构建dp表（简化展示关键列）：

✅dp[3][11] = true，返回true

再看nums = [1,2,3,5]：

• sum = 11（奇数）→ 直接返回false✅

5.2 边界处理

• 单元素：n<2→false
• 总和奇数：直接false
• 最大元素过大：maxNum > target→false
• 全1数组：如[1,1]→target=1，dp[1][1]=true→true

六、时间复杂度与空间复杂度分析（方法一）

时间复杂度：O(n × target)

• 外层循环：n 次；
• 内层循环：target 次；
• 每次操作：O(1)；
• 总计：O(n × target)

根据约束：

• n ≤ 200
• nums[i] ≤ 100→sum ≤ 20000→target ≤ 10000

最坏操作次数：200 × 10000 =2,000,000，在 Java 中完全可接受。

空间复杂度：O(n × target)

• 二维布尔数组：n × (target+1)
• 最坏：200 × 10001 ≈2,000,200 个 boolean≈ 2MB（每个 boolean 实际占 1 byte）
• 总计：O(n × target)

虽可接受，但可进一步优化。

七、答案构思：方法二 —— 一维动态规划（空间优化）

7.1 优化思想

观察状态转移方程：

• dp[i][j]仅依赖于dp[i-1][j]和dp[i-1][j - num]
• 即当前行只依赖上一行

因此，可用一维数组dp[j]代替二维数组，通过倒序遍历避免覆盖未使用的状态。

7.2 为何要倒序遍历？

若正序遍历：

for(intj=num;j<=target;j++){dp[j]=dp[j]||dp[j-num];// dp[j - num] 已被更新！}

此时dp[j - num]是当前轮的值，而非上一轮，导致错误（相当于完全背包）。

而倒序遍历：

for(intj=target;j>=num;j--){dp[j]=dp[j]||dp[j-num];// dp[j - num] 仍是上一轮的值}

确保使用的是未更新的旧状态，符合 0-1 背包要求。

八、完整答案（方法二：一维DP）

publicclassSolution{publicbooleancanPartition(int[]nums){intn=nums.length;if(n<2)returnfalse;intsum=0,maxNum=0;for(intnum:nums){sum+=num;maxNum=Math.max(maxNum,num);}if(sum%2!=0)returnfalse;inttarget=sum/2;if(maxNum>target)returnfalse;// dp[j]: 能否组成和 jboolean[]dp=newboolean[target+1];dp[0]=true;// 和为0总是可行for(intnum:nums){// 倒序遍历，防止重复使用for(intj=target;j>=num;j--){dp[j]=dp[j]||dp[j-num];}}returndp[target];}}

代码优势

• 空间复杂度降至 O(target)；
• 代码更简洁；
• 性能更优（缓存友好）。

九、代码分析（方法二）

9.1 状态更新过程

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

初始：dp = [T, F, F, ..., F]（长度12）

• 处理1：j=11→1，dp[1] = T
• 处理5：j=11→5，dp[6]=T（因dp[1]=T），dp[5]=T
• 处理11：j=11，dp[11] = dp[11] || dp[0] = F || T = T
• 处理5：j=11→5，dp[11]已为 T，保持

最终dp[11] = true✅

9.2 为何dp[0] = true是关键？

因为当j == num时，dp[j] = dp[j] || dp[0]。若dp[0] = false，则无法选中单个元素等于target的情况。

例如nums = [11],target=11：

• dp[0]=true
• 处理11：j=11，dp[11] = F || dp[0] = T→ 正确

十、常见问题解答（FAQ）

Q1：为什么不能用贪心？比如排序后从大到小分配？

A：贪心在此问题中不成立。反例：nums = [6,5,5,4,4]，总和=24，target=12。

• 贪心：先取6，剩余需6 → 取5（剩1）→ 无法完成；
• 实际解：[6,4,4]和[5,5]→ 可行。

NP 完全问题通常无法用贪心解决。

Q2：一维DP中，内层循环为何从target到num？

A：为了确保dp[j - num]是上一轮（即未包含当前num）的状态。若正序，则dp[j - num]可能已被当前num更新过，导致同一元素被多次使用（变成完全背包）。

Q3：如果数组包含负数，还能用此方法吗？

A：不能。因为：

• 背包容量不能为负；
• 状态转移范围不确定；
• 需要其他方法（如 DFS + 记忆化）。

但本题限定为正整数，故安全。

Q4：能否提前终止？

A：可以！在内层循环中，若dp[target]已为true，可提前返回。但最坏情况仍需完整遍历。

十一、优化思路拓展

11.1 位运算优化（Bitset）

由于dp是布尔数组，可用BitSet或位掩码优化。

publicbooleancanPartition(int[]nums){// ... 剪枝同上 ...BitSetbits=newBitSet(target+1);bits.set(0);for(intnum:nums){bits.or(bits.get(0,target-num+1)<<num);if(bits.get(target))returntrue;}returnbits.get(target);}

原理：bits的第j位表示能否组成和j。每次将现有状态左移num位后或运算，相当于加入新元素。

优点：常数级优化，适合target较大时。

11.2 DFS + 记忆化

也可用递归：

privateBoolean[][]memo;publicbooleancanPartition(int[]nums){// ... 剪枝 ...memo=newBoolean[n][target+1];returndfs(nums,0,target);}privatebooleandfs(int[]nums,intindex,intremain){if(remain==0)returntrue;if(index==nums.length||remain<0)returnfalse;if(memo[index][remain]!=null)returnmemo[index][remain];booleanres=dfs(nums,index+1,remain)||dfs(nums,index+1,remain-nums[index]);memo[index][remain]=res;returnres;}

时间复杂度相同，但递归栈可能溢出（n=200 安全）。

11.3 并行化？

由于状态依赖，难以并行。但若只需求是否存在，可分治（如 Meet-in-the-Middle），将时间降至 O(2^{n/2})，适合n较小但target极大时。

十二、数据结构与算法基础知识点回顾

12.1 0-1 背包问题

• 特点：每件物品最多选一次；
• 状态转移：dp[j] = max(dp[j], dp[j-w] + v)（最大化）或dp[j] = dp[j] || dp[j-w]（判定）；
• 空间优化：倒序遍历。

本题是其判定版本。

12.2 NP 完全问题

• P 问题：多项式时间可解；
• NP 问题：多项式时间可验证；
• NP 完全：所有 NP 问题可在多项式时间归约到它。

Partition Problem 是 Karp’s 21 个 NP 完全问题之一。

12.3 动态规划的适用条件

• 最优子结构：全局最优包含子问题最优；
• 重叠子问题：子问题重复出现；
• 无后效性：当前状态与未来无关。

本题满足所有条件。

12.4 空间优化技巧

• 滚动数组：状态仅依赖前 k 行；
• 一维化：倒序/正序控制依赖方向；
• 位运算：布尔状态压缩。

十三、面试官提问环节（模拟对话）

面试官：你说这是 NP 完全问题，那为什么你的解法是 O(n×target)？这不是多项式吗？

答：这是伪多项式时间。多项式时间应仅与输入长度（即 n）相关，而target可达 10⁴，其二进制表示长度仅为 log(target) ≈ 14 位。因此，O(n×target) 实际是指数级（相对于输入规模）。真正的多项式算法应为 O(n^k)，与数值大小无关。

面试官：一维DP中，如果我把内层循环写成正序，会发生什么？

答：会变成完全背包问题，即每个元素可无限次使用。例如nums=[2],target=4，正序会得到dp[4]=true（用了两次2），但本题要求每个元素只能用一次，故错误。

面试官：如果数组很大（n=1000），但数字很小（≤10），你的算法还高效吗？

答：非常高效！因为target ≤ 1000×10/2 = 5000，时间复杂度 O(1000×5000)=5e6，完全可接受。DP 的效率取决于target，而非n。

面试官：如何修改代码以返回具体的分割方案？

答：需记录路径。可在二维DP中回溯：从dp[n-1][target]开始，若dp[i][j] != dp[i-1][j]，说明选了nums[i]，然后跳到dp[i-1][j-nums[i]]。一维DP难以回溯，建议用二维或额外 parent 数组。

十四、这道算法题在实际开发中的应用

14.1 资源分配

在云计算中，将虚拟机分配到两台物理机，使 CPU/内存负载均衡，可建模为本题（若资源可量化为整数）。

14.2 金融对账

银行需将交易记录分为两组，使借贷平衡。若每笔交易金额为整数，可转化为分割等和问题。

14.3 游戏开发

在 RPG 游戏中，将道具分配给两名玩家，使总价值相等，提升公平性。

14.4 编译器优化

在指令调度中，将基本块分配到两个执行单元，使计算量均衡，可近似为本题。

14.5 数据分片

分布式系统中，将数据块分配到两个节点，使存储/计算负载均衡，若块大小为整数，可用此模型。

十五、相关题目推荐

十六、总结与延伸

16.1 核心收获

• NP 完全问题可通过伪多项式 DP解决；
• 0-1 背包是解决子集和问题的标准模型；
• 空间优化（一维DP + 倒序）是背包问题的关键技巧；
• 预处理剪枝能显著提升效率。

16.2 延伸思考

• k 分割问题：将数组分为 k 个等和子集（LeetCode 698），需回溯 + 剪枝；
• 近似算法：若不要求精确相等，可用贪心或随机化算法；
• 在线版本：数据流式到达，需动态维护可行性（极难）。

16.3 给读者的建议

• 理解问题转化：从“分割”到“子集和”是关键一步；
• 掌握背包模板：0-1、完全、多重背包是算法基石；
• 重视边界测试：奇数和、大元素、单元素等；
• 面试中先写二维DP，再优化到一维，展示思考过程。

结语：分割等和子集是一道承上启下的经典题。它连接了理论计算机科学（NP 完全）与实用算法（动态规划），是检验算法功底的试金石。掌握它，你就掌握了处理子集和问题的通用钥匙。希望本文能助你在算法之路上走得更稳、更远！