.jpg)
751 字
4 分钟
分割等和子集
题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
解题思路
- 问题转化：
- 计算数组总和，若为奇数直接返回false
- 目标和 = 总和/2，转换为背包问题
- 动态规划：
- 定义dp[j]表示能否凑出和为j
- 初始化dp=true（空集和为0）
- 状态转移：
- 逆序遍历j从目标值到nums[i]
- dp[j] = dp[j] || dp[j - nums[i]]
- 提前终止：
- 若dp[target]提前为true，直接返回
- 若最大值>target，直接返回false
关键洞察
- 等价子集和：
- 分割等和 ⇔ 存在子集和为sum/2
- 转化为0-1背包可行性问题
- 状态压缩：
- 使用一维DP数组节省空间
- 逆序遍历避免状态覆盖
- 数学性质：
- 总和为奇数必定不可分
- 最大值>sum/2必定不可分
- 贪心剪枝：
- 提前终止减少无效计算
- 时间复杂度优化至O(n×target)
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(n×target)：n为数组长度，target=sum/2 |
| 空间复杂度 | O(target)：DP数组大小为目标值 |
代码实现
var canPartition = function (nums) { const n = nums.length; if (n < 2) return false;
let sum = 0, maxSum = 0; for (const num of nums) { sum += num; if (num > maxSum) maxSum = num; // 修复最大值计算 }
if (sum % 2 !== 0) return false; // 更清晰的奇数判断
const target = sum / 2; if (maxSum > target) return false;
const dp = new Array(target + 1).fill(false); dp[0] = true;
for (const num of nums) { // 提前终止优化：当找到目标组合时提前结束 if (dp[target]) return true; // 反向遍历避免覆盖未处理的数据 for (let j = target; j >= num; j--) { dp[j] = dp[j] || dp[j - num]; // 简化布尔运算 } }
return dp[target];};变种：输出分割方案
const partitionSolution = (nums) => { const sum = nums.reduce((acc, num) => acc + num, 0); if (sum % 2 !== 0) return null;
const target = sum / 2; const dp = Array(target + 1).fill(false); const path = Array(nums.length).fill().map(() => Array(target + 1).fill(false));
dp[0] = true;
for (let i = 0; i < nums.length; i++) { for (let j = target; j >= nums[i]; j--) { if (!dp[j] && dp[j - nums[i]]) { dp[j] = true; path[i][j] = true; // 标记nums[i]被使用 } } }
if (!dp[target]) return null;
// 回溯构造解 const subset = []; let j = target; for (let i = nums.length - 1; i >= 0; i--) { if (path[i][j]) { subset.push(nums[i]); j -= nums[i]; } } return subset;};实际应用场景
- 服务器负载均衡：将任务分割成两组相同处理时间的任务集`
- 公平资源分配：将资源分成价值相等的两份`
- 数据分片优化：数据库水平分区时平衡数据量`
- 财务管理：分割资产使两份资产总值相等`