分割等和子集（Partition Equal Subset Sum）

**题目难度：**中等

题目描述

给定一个包含 (n) 个正整数的数组。请判断是否可以将数组中的所有元素划分为两个子集，使两个子集的元素和相等。

数组中的每个元素必须恰好属于其中一个子集。若可以完成划分，输出 true；否则输出 false。

输入格式

第一行包含一个整数 (n)，表示数组的元素个数。

第二行包含 (n) 个整数，表示数组中的元素。

输出格式

如果可以将数组划分为两个元素和相等的子集，输出 true；否则输出 false。

数据范围

• (1 \le n \le 200)
• (1 \le \text{数组中的每个元素} \le 100)

样例 1

输入

4
1 5 11 5

输出

true

说明

可以将数组划分为 [1, 5, 5] 和 [11]，两个子集的元素和都是 (11)。

样例 2

输入

4
1 2 3 5

输出

false

说明

无法将数组划分为两个元素和相等的子集。 | 测试点编号 | 数据层级 | n | 数据特征 | 标准输出 | 设计目的 | | ----- | ---- | --: | -------------------------- | ------- | -------------------- | | 1 | 弱数据 | 1 | 单元素 2，总和为偶数但无法划分 | false | 检查最小规模和单元素边界 | | 2 | 弱数据 | 5 | 总和为奇数 | false | 检查奇数总和的快速判定 | | 3 | 正常数据 | 4 | 存在重复值，元素 11 恰好等于目标和 | true | 检查典型可行划分 | | 4 | 正常数据 | 4 | 总和为偶数，但不存在目标子集 | false | 防止误认为总和为偶数就一定可分 | | 5 | 压力数据 | 100 | 所有元素均为 1000，目标和为 50000 | true | 检查较大规模、重复值及 0/1 背包更新 |