C++如何将数组平分为两个和相等的子集-C++-PHP中文网

该问题本质是判断能否将数组划分为两个和相等的子集，等价于是否存在子集和为 total_sum / 2；需先验证 total_sum 是否为偶数，否则直接返回 false；使用一维布尔 dp 数组，倒序更新以避免重复选元素，最终返回 dp[target]。

c++如何将数组平分为两个和相等的子集

这个问题本质是 0-1 背包的变形

直接判断能否划分为两个和相等的子集，等价于：是否存在一个子集，其元素和恰好为 total_sum / 2。前提是 total_sum 必须为偶数，否则不可能平分。

所以第一步永远是检查 sum % 2 != 0 —— 如果成立，直接返回 false，不用往下算。

用 `std::vector<bool></bool>` 做空间优化的 DP

目标和记为 target = sum / 2，我们只需要一维布尔数组 dp，其中 dp[j] 表示能否凑出和为 j 的子集。

初始化：dp[0] = true（和为 0 总是可以，选空集），其余为 false
遍历每个数 num 时，必须倒序更新 j 从 target 到 num，避免重复使用同一元素
状态转移：若 dp[j - num] 为 true，则置 dp[j] = true

示例关键片段：

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

int sum = std::accumulate(nums.begin(), nums.end(), 0);
if (sum % 2 != 0) return false;
int target = sum / 2;
std::vector<bool> dp(target + 1, false);
dp[0] = true;
for (int num : nums) {
    for (int j = target; j >= num; --j) {
        if (dp[j - num]) dp[j] = true;
    }
}
return dp[target];
</bool>

注意 `int` 溢出和 `target` 过大的边界情况

如果数组元素和很大（比如全为 1e5 的 200 个数），target 可能超过 1e7，此时 std::vector<bool></bool> 虽省空间但遍历慢，且可能触发栈溢出或超时。

实际编码前先加保护：若 target > 10000，建议直接返回 false 或改用折半搜索（meet-in-the-middle）
nums 全为正整数是前提；含负数或零需另做处理，本题通常默认正整数
某些 OJ 测试用例会故意让 sum 是奇数但非常大，sum / 2 截断后仍是合法 int，但逻辑上已不可分——所以务必先判奇偶

递归 + 记忆化不是最优解，但便于调试逻辑

如果你在验证思路或小数据调试，可以用 unordered_map 记录 (index, remaining) 状态，但要注意键构造开销大、常数高。

参数顺序很重要：先传当前下标 i，再传剩余目标 rem，避免重复计算相同子问题
剪枝条件必须写全：除了 rem == 0 返回 true，还要有 rem 或 <code>i == n 且 rem > 0 时返回 false
不要用 vector<vector>></vector> 做记忆表——rem 可能很大，二维数组会炸内存