【力扣100题】49.分割等和子集

题目描述

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

示例：

• 输入：nums = [1,5,11,5]→ 输出：true（数组可以分割成[1, 5, 5]和[11]）
• 输入：nums = [1,2,3,5]→ 输出：false（数组不能分割成两个元素和相等的子集）

解题思路总览

本题采用**动态规划（0-1背包）**方法。

核心思路转化

将原问题转化为：是否可以从数组中选取若干元素，使得它们的和等于 sum/2？

• 如果能找到一个子集的和为 sum/2，那么剩下的元素和也是 sum/2，问题得解
• 这就是一个「0-1背包」问题：每个数只能用一次，问能否装满容量为 sum/2 的背包

完整代码

classSolution{public:boolcanPartition(vector<int>&nums){intsum=0;for(inti=0;i<nums.size();i++)sum+=nums[i];if(sum%2==1)returnfalse;vector<int>dp(10001,0);for(inti=0;i<nums.size();i++){for(intj=sum/2;j>=nums[i];j--){dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);}}if(dp[sum/2]==sum/2)returntrue;returnfalse;}};

算法流程图

输入: nums = [1, 5, 11, 5] 计算总和: sum = 1 + 5 + 11 + 5 = 22 sum % 2 == 0? 是 target = sum / 2 = 11 初始化: dp[0...11] = 0 容量为 11 的背包 遍历数组: i = 0, nums[0] = 1: j = 11: j >= 1, dp[11] = max(dp[11], dp[10]+1) = 1 j = 10: j >= 1, dp[10] = max(dp[10], dp[9]+1) = 1 ... j = 1: j >= 1, dp[1] = max(dp[1], dp[0]+1) = 1 dp[1] = 1 i = 1, nums[1] = 5: j = 11: j >= 5, dp[11] = max(dp[11], dp[6]+5) = 6 j = 10: j >= 5, dp[10] = max(dp[10], dp[5]+5) = 6 ... j = 5: j >= 5, dp[5] = max(dp[5], dp[0]+5) = 5 dp[5] = 5 i = 2, nums[2] = 11: j = 11: j >= 11, dp[11] = max(dp[11], dp[0]+11) = 11 dp[11] = 11 i = 3, nums[3] = 5: j = 11: j >= 5, dp[11] = max(dp[11], dp[6]+5) = 11 (不更新) ... 最终 dp[11] = 11 dp[11] == target == 11? 是 返回 true

逐行解析

intsum=0;for(inti=0;i<nums.size();i++)sum+=nums[i];

含义：计算数组所有元素的总和。

if(sum%2==1)returnfalse;

含义：如果总和是奇数，无法平分成两个和相等的子集，直接返回 false。

vector<int>dp(10001,0);

含义：创建背包容量数组。dp[j]表示容量为j的背包最多能装多少重量的物品（元素和）。这里dp大小设为 10001 是因为sum <= 200 × 100 = 20000，所以sum/2 <= 10000。

for(inti=0;i<nums.size();i++)

含义：遍历数组中的每个元素（物品）。

for(intj=sum/2;j>=nums[i];j--)

含义：0-1 背包的关键：内层循环倒序遍历背包容量。这样可以保证每个元素只被使用一次（正序会导致完全背包问题）。

dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);

含义：状态转移方程。对于当前元素nums[i]，要么不放入背包（保持dp[j]），要么放入背包（dp[j - nums[i]] + nums[i]）。取较大值更新。

if(dp[sum/2]==sum/2)returntrue;

含义：遍历结束后，如果dp[sum/2]恰好等于sum/2，说明可以找到一个子集的和为sum/2，返回 true。

returnfalse;

含义：无法找到和为sum/2的子集，返回 false。

为什么内层循环要倒序？

以 nums = [1, 5] 为例，target = 3 正序（错误）： i=0, num=1: dp[1] = max(dp[1], dp[0]+1) = 1 dp[2] = max(dp[2], dp[1]+1) = 2 <- 用到了本轮刚更新的 dp[1] dp[3] = max(dp[3], dp[2]+1) = 3 <- 用到了本轮刚更新的 dp[2] 结果：num=1 被使用了多次！变成完全背包了 倒序（正确）： i=0, num=1: dp[3] = max(dp[3], dp[2]+1) dp[2] 还是旧值 dp[2] = max(dp[2], dp[1]+1) dp[1] 还是旧值 dp[1] = max(dp[1], dp[0]+1) = 1 结果：num=1 只被使用一次

复杂度分析

面试追问 FAQ

相关题目

总结