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

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%21)returnfalse;不可能平分三、0/1 背包建模概念对应物品数组中的每个数重量数值大小nums[i]价值数值大小nums[i]背包容量target sum / 2✅判断是否能恰好装满容量为target的背包四、DP 定义dp[j]容量为 j 的背包能装的最大价值目标dp[target]target五、状态转移方程dp[j]max(dp[j],// 不选当前数dp[j-nums[i]]nums[i]// 选当前数)六、遍历顺序非常重要for(inti0;in;i){for(intjtarget;jnums[i];j--){dp[j]Math.max(dp[j],dp[j-nums[i]]nums[i]);}}✅j 必须从大到小防止同一物品被重复使用保证是 0/1 背包✅ AC 代码JavaclassSolution{publicbooleancanPartition(int[]nums){intsum0;for(intnum:nums){sumnum;}// 奇数不可能平分if(sum%21)returnfalse;inttargetsum/2;int[]dpnewint[20001];// dp[j]: 容量为 j 的最大价值和// 0/1 背包for(inti0;inums.length;i){for(intjtarget;jnums[i];j--){dp[j]Math.max(dp[j],dp[j-nums[i]]nums[i]);}}returndp[target]target;}}⏱️ 复杂度分析指标复杂度时间复杂度O(n × sum)空间复杂度O(sum)⚠️ 时间复杂度不是O(n²)而是由数值总和决定✅ 核心总结一句话把“能否平分数组”转化为“是否存在子集和为 sum/2”再用 0/1 背包判断是否恰好装满。