平分子集

题目描述

给定一个只包含正整数的非空数组 nums，如果你可以把这个数组分割成两个子集，使得两个子集的元素和相等，返回 true，否则返回 false。

输入格式

第一行一个 $n$，表示数组里数据个数。（$1 \le n \le 200$）

后面一行 $n$ 个正整数 $nums[i]$（$1 \le nums[i] \le 100$）。

输出格式

输出 true 如果你可以把这个数组分割成两个子集，使得两个子集的元素和相等，否则输出 false。

样例输入 1

4
1 5 11 5

样例输出 1

true

样例解释 1

所有数的和是 $22$，平均分成两份每份 $11$：{11} 与 {1, 5, 5} 这两组子集的元素和都是 $11$，所以输出 true。

样例输入 2

4
1 2 3 5

样例输出 2

false

样例解释 2

所有数的和是 $11$，是奇数，不可能平分成两份相等的整数和，所以输出 false。

样例输入 3

6
1 1 1 1 1 1

样例输出 3

true

样例输入 4

3
10 20 35

样例输出 4

false

数据范围

• $1 \le n \le 200$
• $1 \le nums[i] \le 100$