LeetCode 416. 分割等和子集
📌 题目描述
题目级别：中等
给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1:
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成[1, 5, 5]和[11]。示例 2:
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
💡 破题思路：转化为 0-1 背包问题
这道题表面上是“分割数组”，但稍加数学转化就能看穿它的本质：
如果数组能够被平分成和相等的两份，那么整个数组的总和sum必须是偶数，且我们要在数组中挑出一部分数字，使得它们的和恰好等于sum / 2。
这就完美契合了0-1 背包问题的模型：
- 背包总容量：
target = sum / 2。 - 物品：数组中的每个数字
nums[i]。 - 物品重量：数字本身的大小。
- 物品价值：依然是数字本身的大小（本题只需关心能否装满，不需要价值最大化，布尔值即可）。
- 核心限制：每个数字只能使用一次（0-1 背包）。
本解法高光点（状态压缩与倒序遍历）：
传统的二维背包需要dp[i][j]记录前i个物品凑成重量j的状态。
但实际上，我们在计算第i行时，仅仅依赖于第i-1行的数据。因此，我们可以直接把二维数组压缩成一维数组dp[j]。
⚠️ 致命细节：在一维数组中，内层循环遍历容量j时，必须从大到小倒序遍历！如果正序遍历，我们在计算dp[j]时，用到的dp[j - nums[i]]可能在这一轮已经被当前物品更新过了，导致一个物品被重复放入（那就变成完全背包了）。倒序遍历完美保证了每个物品只被放入一次。
💻 C++ 代码实现 (满分标准模板)
classSolution{public:boolcanPartition(vector<int>&nums){intn=nums.size();intsum=0,ma=0;// 1. 计算总和并寻找最大元素for(inti=0;i<n;i++){sum+=nums[i];ma=max(ma,nums[i]);}// 2. 极致剪枝 (大厂面试加分项)// 如果总和是奇数，绝对不可能平分if(sum%2!=0)returnfalse;inttarget=sum/2;// 如果数组中最大的元素直接比目标和还要大，那肯定凑不出来if(ma>target)returnfalse;// 3. 一维 DP 数组// dp[j] 表示能否从数组中挑选出和为 j 的子集vector<bool>dp(target+1,false);// 核心起跑点：什么都不挑，凑出和为 0 永远是 Truedp[0]=true;// 外层循环：遍历每一个数字 (物品)for(inti=0;i<n;i++){// 内层循环：遍历背包容量。必须【倒序】，防止数字被重复使用！// 优化：j 只需要遍历到 nums[i]，因为比 nums[i] 还小的容量根本装不下当前物品for(intj=target;j>=nums[i];j--){// 状态转移：能否凑出 j，取决于原来就能凑出 j，或者能凑出 (j - 当前数字)dp[j]=dp[j]||dp[j-nums[i]];}}returndp[target];}};
 零基础入门：核心原理、训练机制与能力全解)
