题意概括

给定一个只包含正整数的非空数组，判断是否能将这个数组分割成两个子集，使得这两个子集的元素和相等。

数据范围:

• $1 \le n \le 200$
• 数组中每个元素的取值范围为 $1$ 到 $100$。

基础知识

这个问题是经典的 0/1 背包问题 的一个变种。

首先，我们可以计算出数组所有元素的总和 $S$。如果我们要将数组分成两个和相等的子集，那么每个子集的和都必须是 $S/2$。

1. 如果总和 $S$ 是一个奇数，那么它不可能被平分成两个整数和的子集，因此可以直接判断为 false。
2. 如果总和 $S$ 是一个偶数，问题就转化为：能否从数组中挑选出若干个元素，使得这些元素的和恰好等于 $T = S/2$。

这就是一个标准的0/1背包问题：我们有一个容量为 $T$ 的背包，和 $n$ 个物品（数组中的每个数字），每个物品的“重量”和“价值”都是它自身的数值。我们需要判断是否能恰好装满这个背包。

我们可以使用动态规划来解决。定义一个布尔数组 $dp$，其中 $dp[j]$ 表示是否可以用数组中的数字凑成和为 $j$。

• 状态定义: $dp[j]$ 是一个布尔值，true 表示可以从数组中选出子集使得和为 $j$，false 表示不可以。
• 状态初始化: $dp[0] = \text{true}$，因为不选任何数，和为0，这是可行的。
• 状态转移: 我们遍历数组中的每一个数字 $x$。对于每个数字 $x$，我们更新 $dp$ 数组。为了凑成新的和 $j$，我们可以考虑是否使用 $x$。如果在使用 $x$ 之前，我们已经能凑成 $j-x$（即 $dp[j-x]$ 为 true），那么加上 $x$ 之后我们就能凑成 $j$。状态转移方程为：$$dp[j] = dp[j] \lor dp[j-x]$$ 为了保证每个数字只被使用一次（0/1背包），我们需要对 $j$ 进行逆序遍历（从 $T$ 到 $x$）。

最终，我们只需要检查 $dp[T]$ 的值即可。如果为 true，则说明可以找到和为 $T$ 的子集，原问题有解。

该算法的时间复杂度为 $O(n \times T)$，空间复杂度为 $O(T)$。

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

void run() {
    int n;
    cin >> n;

    vector<int> a(n);
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sum += a[i];
    }

    // 如果总和为奇数，不可能平分
    if (sum % 2 != 0) {
        cout << "false" << endl;
        return;
    }

    int tar = sum / 2;
    vector<bool> dp(tar + 1, false);

    // dp[0] 表示和为0是可达的（不选任何元素）
    dp[0] = true;

    // 0/1 背包过程
    for (int x : a) {
        // 必须倒序遍历，防止一个物品被多次使用
        for (int j = tar; j >= x; --j) {
            dp[j] = dp[j] || dp[j - x];
        }
    }

    if (dp[tar]) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }
}

int main() {
    // 关闭同步流
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    run();

    return 0;
}

/*
样例 1:
输入:
4
1 5 11 5
输出:
true

样例 2:
输入:
4
1 2 3 5
输出:
false
*/