时间限制： 3.0 秒

空间限制： 512 MB

题目描述

给定 $n$ 个正整数，其和为 $sum$，问是否能在其中选出 $m~(1 \le m \le n)$ 个数，使得这 $m$ 个数的和为 $\frac {sum}2$。

输入格式

从标准输入读入数据。

第一行给出一个正整数 $n~(1 \le n \le 200)$。

第二行给出 $n$ 个 $\le 10^6$ 的正整数，以单个空格隔开。

输出格式

输出到标准输出。

如果能选出满足要求的 $m$ 个数，输出 YES；否则输出 NO。

4
10 21 42 31

YES

样例 1 解释

其中 $\{10,42\}$ 以及 $\{21,31\}$ 即为所求。

提示

邓俊辉《习题解析》[1-16]

显然 (a) 小问给出的蛮力枚举复杂度为 $O(2^n)$，这在本题当中是不可接受的。(b) 小问也说明了该问题被证明是 NP-complete 的，因此对 $n$ 而言不存在多项式规模解法。

不过对于本题而言，由于 $n$ 的规模较小，首先可以考虑对蛮力搜索进行剪枝；其次，所有正整数的总和是有值域上限的，该问题也可以被规约为 01-背包问题，所以可以考虑利用可达性 01 背包问题的解法，利用位图（bitset）结构优化来解决本问题。