本题要求判断一个只包含正整数的非空数组能否被分割成两个子集，使得两个子集的元素和相等。换句话说，我们需要判断是否存在一个子集，其和为整个数组和的一半。

算法思路

问题转化

• 先计算数组所有元素的和 sum。如果 sum 为奇数，则不能分成两个和相等的子集，直接返回 false。
• 如果 sum 为偶数，则问题转化为「是否存在一个子集，其元素和等于 sum/2」。

动态规划（背包问题）

• 定义状态：dp[i] 表示是否存在子集，使得子集元素和为 i。

题目内容

给定一个只包含正整数的非空数组 $nums$ ，判断该数组是否可以被分割成两个子集，使得两个子集的元素和相等。

输入描述

第一行一个整数 $n$ ，表示 $nums$ 的长度。

第二行表示 $nums$ ，数字之间用空格隔开。

输出描述

$nums$ 可以被分割成两个子集，输出 $true$ ；否则输出 $false$ 。

样例1

输入

4
1 5 11 5

输出

true