【力扣100题】49.分割等和子集
题目描述给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。示例输入nums [1,5,11,5]→ 输出true数组可以分割成[1, 5, 5]和[11]输入nums [1,2,3,5]→ 输出false数组不能分割成两个元素和相等的子集解题思路总览方法思路时间复杂度空间复杂度动态规划0-1背包转化为是否能从数组中选取若干元素使其和等于 sum/2O(n × sum/2)O(sum/2)DFS 剪枝从数组中尝试选取元素看能否凑到目标值O(2^n)O(n)位运算优化用 bitset 优化空间适合 sum 较小的情况O(n × sum/32)O(sum/32)本题采用**动态规划0-1背包**方法。核心思路转化将原问题转化为是否可以从数组中选取若干元素使得它们的和等于 sum/2如果能找到一个子集的和为 sum/2那么剩下的元素和也是 sum/2问题得解这就是一个「0-1背包」问题每个数只能用一次问能否装满容量为 sum/2 的背包完整代码classSolution{public:boolcanPartition(vectorintnums){intsum0;for(inti0;inums.size();i)sumnums[i];if(sum%21)returnfalse;vectorintdp(10001,0);for(inti0;inums.size();i){for(intjsum/2;jnums[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逐行解析intsum0;for(inti0;inums.size();i)sumnums[i];含义计算数组所有元素的总和。if(sum%21)returnfalse;含义如果总和是奇数无法平分成两个和相等的子集直接返回 false。vectorintdp(10001,0);含义创建背包容量数组。dp[j]表示容量为j的背包最多能装多少重量的物品元素和。这里dp大小设为 10001 是因为sum 200 × 100 20000所以sum/2 10000。for(inti0;inums.size();i)含义遍历数组中的每个元素物品。for(intjsum/2;jnums[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 正序错误 i0, num1: 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] 结果num1 被使用了多次变成完全背包了 倒序正确 i0, num1: 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 结果num1 只被使用一次复杂度分析复杂度值说明时间复杂度O(n × sum/2)外层循环 n 次内层循环 sum/2 次空间复杂度O(sum/2)dp 数组大小为 sum/2 1面试追问 FAQ问题答案为什么能转化成 0-1 背包问题如果能找到和为 sum/2 的子集剩下的元素和也是 sum/2所以问题等价于「能否从数组中选若干元素使其和为 sum/2」dp[j]的含义是什么容量为 j 的背包最多能装多少重量的物品即最多能达到多大的和为什么不直接用布尔数组dp[j]表示能否凑到 j因为dp[j]表示「最多」能装多少可以用来判断是否恰好装满布尔数组需要额外记录具体方案dp[sum/2] sum/2为什么能判断「恰好装满」dp[sum/2]是背包最多能装到的重量如果它等于sum/2说明可以恰好装满进阶如何输出具体的分割方案额外记录每个状态的选择路径从dp[sum/2]开始回溯找出被选中的元素进阶如何优化空间使用 bitsetbitset10001 bits; bits[0] 1; bits相关题目题号题目难度核心思路416分割等和子集中等0-1 背包322零钱兑换中等完全背包279完全平方数中等动态规划494目标和中等0-1 背包计数1049最后一块石头的重量 II中等0-1 背包总结要点内容核心思想将分割等和子集转化为 0-1 背包能否从数组中选若干元素使其和为 sum/2状态定义dp[j] 容量为 j 的背包最多能装的重量元素和状态转移dp[j] max(dp[j], dp[j-nums[i]] nums[i])关键点内层循环倒序保证每个元素只使用一次边界条件sum 为奇数时直接返回 false结果判断dp[sum/2] sum/2表示恰好装满
)
