企业官网建设流程全解析

LeetCode 416：分割等和子集 —— （0-1背包）

🔗 题目链接

👉 https://leetcode.cn/problems/partition-equal-subset-sum/

📖 内容概要

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

✅ 使用0/1 背包思想
✅ 一维 DP 优化
✅ 时间复杂度 O(n × sum)
✅ 空间复杂度 O(sum)

💡 解题思路

一、问题转化（最关键一步）

能否从数组中选出若干个数，使其和等于sum / 2

如果能，那么剩下的数之和也一定是sum / 2。

二、可行性剪枝

• 如果数组总和是奇数：

  if(sum%2==1)returnfalse;

• 不可能平分

三、0/1 背包建模

✅判断是否能恰好装满容量为target的背包

四、DP 定义

dp[j]=容量为 j 的背包，能装的最大价值

目标：

dp[target]==target

五、状态转移方程

dp[j]=max(dp[j],// 不选当前数dp[j-nums[i]]+nums[i]// 选当前数)

六、遍历顺序（非常重要）

for(inti=0;i<n;i++){for(intj=target;j>=nums[i];j--){dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);}}

✅j 必须从大到小

• 防止同一物品被重复使用
• 保证是 0/1 背包

✅ AC 代码（Java）

classSolution{publicbooleancanPartition(int[]nums){intsum=0;for(intnum:nums){sum+=num;}// 奇数不可能平分if(sum%2==1)returnfalse;inttarget=sum/2;int[]dp=newint[20001];// dp[j]: 容量为 j 的最大价值和// 0/1 背包for(inti=0;i<nums.length;i++){for(intj=target;j>=nums[i];j--){dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);}}returndp[target]==target;}}

⏱️ 复杂度分析

⚠️ 时间复杂度不是O(n²)，而是由数值总和决定

✅ 核心总结一句话

把“能否平分数组”转化为“是否存在子集和为 sum/2”，再用 0/1 背包判断是否恰好装满。