C++如何判断数组是否可以分成和相等的两部分-C++-PHP中文网

先判断总和是否为偶数，否则直接返回false；再用动态规划求解能否选出若干数使其和等于总和的一半，状态dp[j]表示能否凑出和j，初始化dp[0]=true，遍历每个数倒序更新。

c++如何判断数组是否可以分成和相等的两部分

先看总和是否为偶数，否则直接不可能

这个问题本质是经典的「分割等和子集」问题，属于 0-1 背包的变种。第一步永远是检查 sum % 2 != 0：如果数组总和是奇数，根本没法拆成两个整数和相等的部分，直接返回 false。

注意别漏掉空数组或单元素场景：sum == 0 时（比如全零数组）是合法的，但需确保数组长度 ≥ 2 才有“两部分”的语义；不过题目通常不严格限定非空划分，所以按算法逻辑走即可。

用动态规划判断能否凑出 target = sum / 2

设 target = sum / 2，问题转化为：能否从数组中选出若干数，使其和恰好等于 target？这是典型的布尔型 0-1 背包，推荐用一维 vector<bool></bool> 优化空间。

初始化 dp[0] = true（和为 0 总是可以达成，不选任何数）
遍历每个数 num，倒序更新 dp[j]（从 target 到 num），避免重复使用同一元素
状态转移：若 dp[j - num] 为 true，则 dp[j] = true

示例：

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

vector<int> nums = {1,5,11,5};
int sum = accumulate(nums.begin(), nums.end(), 0); // 22 → target = 11
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;
    }
}
// 最终 dp[11] == true → 可分</bool></int>

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

虽然题目常给小数据，但实际编码要防一手：sum 可能超出 int 范围（尤其 vector<int></int> 元素全为大正数），建议用 long long 算总和再判断是否可被 2 整除；另外如果 target 太大（比如 > 1e4），DP 数组可能爆内存或超时，此时应优先考虑剪枝或换用 DFS+记忆化（带 sum/2 剪枝）。