Abc 374 C - Separated Lunch

由于 KEYENCE 总部的员工越来越多，他们决定将总部各部门分成两组，错开午休时间。

KEYENCE 总部有 N 个部门，第 i 个部门（1≤i≤N）的人数为 K i 。

当将每个部门分配到 A 组或 B 组时，让每个组同时午休，并确保 A 组和 B 组的午休时间不重叠，求出同时午休的最大人数的最小可能值。

换句话说，求出以下两个值中较大者的最小可能值：分配到 A 组的部门总人数和分配到 B 组的部门总人数。

约束

2≤N≤20

1≤K i ≤10 8

所有输入值都是整数。

输入

输入来自标准输入，格式如下：

N

K 1 K 2… K N

输出

打印同时午休的最大人数的最小可能值。

示例输入 1

5

2 3 5 10 12

示例输出 1

17

当将部门 1、2 和 5 分配给 A 组，将部门 3 和 4 分配给 B 组时，A 组共有

2+3+12=17 人，B 组共有 5+10=15 人。因此，同时午休的最大人数为 17。

无法分配部门以使两组都有16 人或更少，因此打印 17。

---

这是一道01背包问题，比赛的时候我用动态规划做了，结果超时了。。

看了下数据范围，N很小，但是K很大，这样的话，他们的和就会很大，如果dp的话，需要遍历每个数，这样就超时了，当时知道超时原因，但是不知道怎么优化啊，N很小，那么可以通过枚举的办法来解决，这时候想到之前的一个方法，也就是数位dp，就是一个字符串，每个数01分别表示选还是不选，但是我不会啊。。。

后来看了其他人的提交，用hashset来存，这样可以保存所有的可能的组合。才恍然大悟。。我怎么就这么笨呢。。