给定一个正整数的集合A={a1,a2,….,an},是否可以将其分割成两个子集合,使两个子集合的数加起来的和相等。例A = { 1, 3, 8, 4, 10} 可以分割:{1, 8, 4} 及 {3, 10}

这是一个经典的哈希表（或称关联数组）应用问题，通常被称为“两分之和”或“partition problem”，可以用动态规划的方法来解决。给定一个整数集合，我们试图找到其中的一半元素之和等于另一半的元素之和。

算法步骤如下：

1. 创建一个空的哈希表`sums`，用于存储每个元素到目标总和的距离（如果存在的话）。
2. 遍历输入集合A中的每一个元素`num`，对于每个元素，检查当前的目标总和`target`是否为`nums[i]`（即元素值本身），如果是，则找到了两个子集的和相等；如果不是，更新哈希表`sums`，使得`sums[target - num]`如果存在则说明能找到这样的分割（因为已经有了`target - num`的和，再加上`num`就达到了`target`）。
3. 如果遍历完整个集合都没有找到满足条件的`target`，则集合A不能被分割成和相等的两部分。

对于你提到的例子A = {1, 3, 8, 4, 10}，我们可以用上述方法检查每个可能的`target`值（从最小元素到最大元素的和的一半）是否存在对应的配对。

#include <unordered_map>

bool canPartition(vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % 2 != 0) return false; // 总和必须是偶数才能被分成两个相等的部分

    unordered_map<int, bool> sums;
    sums[0] = true;

    for (int num : nums) {
        for (auto it = sums.lower_bound(sum / 2 - num); it != sums.end(); ++it) {
            if (*it == sum / 2 - num) {
                return true; // 找到了一对和为目标一半的数
            }
            sums[*it + num] = true;
        }
    }

    return false;
}

// 示例用法
vector<int> A = {1, 3, 8, 4, 10};
if (canPartition(A)) {
    cout << "集合可以分割成和相等的两部分" << endl;
} else {
    cout << "集合无法分割成和相等的两部分" << endl;
}