一、题目416. 分割等和子集 - 力扣LeetCode二、做题思路1. 问题转化前置分析要将数组分割成两个和相等的子集等价于从数组中选出一些数使它们的和等于总和的一半。设总和为sum若sum为奇数则不可能平分直接返回false。若为偶数目标值aim sum / 2。于是问题转化为一个01背包可行性问题有n个物品每个物品重量数值为nums[i]背包容量为aim问能否恰好装满。2. 状态表示核心基础包含推导思路如何想到用dp[i][j]我们需要记录处理到第几个数以及当前已经凑出的和是多少。对于每个数只有“选”或“不选”两种决策这符合 01 背包的特征。因此定义dp[i][j]表示从前i个数中选取能否凑出总和恰好为jtrue表示可行false表示不可行。这里i范围从 0 到n0 表示一个数都不选j范围从 0 到aim。这个状态能覆盖所有前缀和组合满足无后效性是解决本问题的出发点。3. 状态转移方程关键难点对于第i个数下标i-1数值nums[i-1]我们决定不选或选不选dp[i][j]继承前i-1个数的结果即dp[i-1][j]。选前提是j nums[i-1]且前i-1个数能凑出j - nums[i-1]即dp[i-1][j - nums[i-1]]为true。只要两者任一为truedp[i][j]即为true。因此转移为dp[i][j] dp[i-1][j] || (j nums[i-1] dp[i-1][j - nums[i-1]])。4. 初始化边界防护当目标j 0时不选任何数即可凑出0因此dp[i][0] true对所有i成立。当i 0没有数可选且j 0时无法凑出任何正数dp[0][j] false默认false即可。代码中通过循环for (int i0; in; i) dp[i][0] true;实现第一列的初始化。5. 填表顺序递推方向dp[i][j]依赖dp[i-1][j]上一行同列和dp[i-1][j - nums[i-1]]上一行左列因此必须按行从上到下i从 1 到n列从左到右j从 1 到aim遍历确保前置状态已就绪。6. 返回值目标映射最终判断dp[n][aim]是否为true即所有数中能否选出若干个数凑成aim。若为true则原数组可等和分割否则不能。代码直接返回dp[n][aim]。三、代码class Solution { public: bool canPartition(vectorint nums) { // 1. 计算数组总和若为奇数则不可能平分 int sum 0; for (auto x : nums) sum x; if (sum % 2 ! 0) return false; int target sum / 2; // 目标子集和 int n nums.size(); // 2. 创建dp表 // dp[i][j] 表示能否从前 i 个元素中选取若干个数使其和恰好为 j vectorvectorbool dp(n 1, vectorbool(target 1, false)); // 3. 初始化 // 前 i 个元素中选出和为 0 的方案总是存在即什么都不选所以 dp[i][0] true for (int i 0; i n; i) { dp[i][0] true; } // 4. 填表顺序外层遍历物品i 从 1 到 n内层遍历容量j 从 1 到 target // 因为 dp[i][j] 依赖于 dp[i-1][j]不选当前数和 dp[i-1][j-nums[i-1]]选当前数 // 所以按行从上到下、列从左到右即可。 for (int i 1; i n; i) { for (int j 1; j target; j) { // 5. 状态转移方程 // 不选第 i 个数继承上一行的状态 dp[i-1][j] // 选第 i 个数前提是 j nums[i-1]且 dp[i-1][j-nums[i-1]] 为 true dp[i][j] dp[i - 1][j]; if (j nums[i - 1]) { dp[i][j] dp[i][j] || dp[i - 1][j - nums[i - 1]]; } } } // 6. 返回值dp[n][target] 表示能否从前 n 个数中选出和为 target 的子集 return dp[n][target]; } };四、流程图五、优化1. 状态表示核心基础包含推导思路若定义二维dp[i][j]表示前i个数能否凑出j观察转移方程发现dp[i][j]只依赖于上一行dp[i-1][...]的值。因此可以压缩为一维数组用滚动更新表示当前处理到的物品。最终我们定义dp[j]表示考虑已处理完的物品能否凑出总和恰好为jtrue可行false不可行。随着物品逐个加入dp[j]不断更新遍历结束后即代表所有物品的状态。2. 状态转移方程关键难点对于当前物品nums[i-1]第i个我们决定是否将其加入子集不选保持原状dp[j]不变等号右边的dp[j]代表上一轮的状态。选前提是j nums[i-1]且上一轮dp[j - nums[i-1]]为true。两者任一满足则dp[j]为true因此转移为dp[j] dp[j] || dp[j - nums[i-1]]j从target逆序到nums[i-1]。3. 初始化边界防护目标j 0不选任何数即可凑出 0因此dp[0] true。其余dp[j]j 0初始化为false表示未处理任何物品时无法凑出正数。一维数组默认全false只需设置dp[0] true即可。4. 填表顺序递推方向关键必须逆序遍历容量j从target到nums[i-1]。因为dp[j]的更新依赖dp[j - nums[i-1]]若从小到大遍历dp[j - nums[i-1]]可能在当前物品的处理中被提前更新导致物品被重复使用违背 01 背包每个物品只能选一次。逆序确保dp[j - nums[i-1]]仍为上一轮未处理当前物品的状态与二维的dp[i-1][j - nums[i-1]]等价。外层遍历物品i从 1 到n内层j从target递减到nums[i-1]。5. 返回值目标映射最终判断dp[target]是否为true即所有数中能否选出若干个数凑成target。若为true则原数组可等和分割否则不能。代码直接返回dp[target]。class Solution { public: bool canPartition(vectorint nums) { // 1. 计算数组总和若为奇数则不可能平分 int sum 0; for (auto x : nums) { sum x; } if (sum % 2 ! 0) { return false; } int target sum / 2; // 目标子集和即背包容量 int n nums.size(); // 2. 创建dp表一维滚动数组 // dp[j] 表示当前已考虑的部分元素中是否存在一个子集其和恰好为 j // 由于使用滚动数组dp[j] 对应二维 dp[i][j] 的当前行状态i为外层循环索引 vectorbool dp(target 1, false); // 3. 初始化 // 和为0总是可达的不选任何元素因此 dp[0] true // 其余 dp[j] 初始为 false表示尚未找到和为 j 的子集 dp[0] true; // 4. 填表顺序 // 外层循环遍历每个物品i 从 1 到 n // 内层循环遍历容量 j 从 target 递减到 nums[i-1]倒序 // 原因dp[j] 依赖于上一行较小容量 dp[j-nums[i-1]] 的状态 // 如果正序更新dp[j-nums[i-1]] 可能已经被当前物品更新过 // 导致每个物品被重复使用违背0/1背包的“每个物品最多选一次”原则。 // 倒序则保证在更新 dp[j] 时用到的 dp[j-nums[i-1]] 仍属于“上一轮”未处理当前物品的状态。 for (int i 1; i n; i) { for (int j target; j nums[i - 1]; j--) { // 5. 状态转移方程一维形式 // 当前容量 j 是否可达取决于 // - 不选第 i 个数dp[j] 保持原值即上一轮的结果对应二维的 dp[i-1][j] // - 选第 i 个数前提是 j nums[i-1]且上一轮容量 j-nums[i-1] 可达即 dp[j-nums[i-1]] 为 true // 如果可达则当前状态 dp[j] 也变为 true dp[j] dp[j] || dp[j - nums[i - 1]]; } } // 6. 返回值dp[target] 表示能否从所有数中选出和为 target 的子集 return dp[target]; } };