题解 | 分割等和子集

#include <iostream>
#include <vector>
#include <algorithm> // 包含max函数
using namespace std;

int main() 
{
    int n, sum = 0, max_num = 0; // n：数组长度；sum：数组总和；max_num：数组中最大元素
    cin >> n; // 读取数组长度
    vector<int> nums(n); // 初始化存储数组的容器
    
    // 1. 读取数组元素，同时计算总和sum和最大元素max_num
    for(int i = 0; i < n; i++)
    {
        cin >> nums[i]; // 读取元素
        max_num = max(max_num, nums[i]); // 更新最大元素
        sum += nums[i]; // 累加计算总和
    }

    // 2. 预处理判断1：若总和为奇数，直接无法分割（两个相等的整数和必为偶数）
    if(sum % 2 != 0)
    {
        cout << "false" << endl;
        return 0;
    }

    // 3. 计算目标和target（总和的一半）
    int target = sum / 2;
    
    // 4. 预处理判断2：若最大元素 > target，无法分割（该元素无法被任何子集包含）
    if(max_num > target)
    {
        cout << "false" << endl;
        return 0;
    }

    // 5. 动态规划：定义dp[j]表示「能否从数组中选出若干元素，使其和为j」
    vector<bool> dp(target + 1, false); // 大小为target+1，初始全为false
    dp[0] = true; // 基准情况：和为0的子集一定存在（空集）

    // 6. 遍历每个元素，更新dp数组（0-1背包逻辑）
    for(int i = 0; i < n; i++) // 遍历每个元素（每个元素只能选一次）
        // 从target倒序遍历到nums[i]：避免同一元素被重复选择（0-1背包核心）
        for(int j = target; j >= nums[i]; j--) 
            // 状态转移：若能组成和为j-nums[i]的子集，加上当前元素nums[i]就能组成和为j的子集
            dp[j] = dp[j] || dp[j - nums[i]];

    // 7. 最终判断：若dp[target]为true，说明存在和为target的子集，即能分割
    cout << (dp[target] ? "true" : "false");
    return 0;
}

1. 预处理优化：总和为奇数时直接返回 false（数学必然性）。最大元素超过 target 时返回 false（该元素无法被任何子集包含，否则子集和会超过 target）。
2. 动态规划设计：dp[j] 的含义：是否存在子集和为 j。初始状态 dp[0] = true：空集的和为 0，是必然存在的。
3. 0-1 背包的倒序遍历：内层循环从 target 倒序到 nums[i]，确保每个元素仅被考虑一次（避免重复选择）。状态转移逻辑：若 dp[j - nums[i]] 为 true（存在和为 j - nums[i] 的子集），则加上当前元素 nums[i] 后，dp[j] 也为 true。