TUG  Tug of War
We want to pick a certain number of people from a group of N people and make them play a game of tug of war!
Then, we would like to split these people into two teams.
Afterwards, an intense game of tug of war would start.
However, when the strength of each team is not equivalent, the game is not very fun. A team's strength is the sum of the strengths of the people in the team.
Since you want the game that is fun, it is necessary to determine if it is possible to pick some people and split them into two teams such that the two teams' strengths are equal.
Input
The input consists of a number of test cases.
The first line is the number of test case, T. (1<=T<=200)
Each case starts with N (1<=N<=100,000), the total number of people.
The next line consists of N integers, separated by a space. The ith integer indicates the strength of the ith person. These integers are less than 100, but larger than 0.
Output
For each test case, output "YES" if it is possible to pick some people from the group and separate into two teams of equal strengths. If not, output "NO". Refer to the sample test cases for further clarifications.
Example
Input: 2
4
10 20 30 40
3
10 18 15
Output: YES
NO
There are a number of ways to pick teams for the first test case. One example would be {10,20} and {30}.
hide comments
yfsyfs:
20200315 17:25:37
knapsack seems does not work~ multiple knapsack with any optimate 

anirudnits:
20181231 16:58:24
Similar problem of sorts ADACOINS, if you're using bitset that is! Have no idea as to how to do it otherwise, any suggestions? Last edit: 20181231 17:00:04 

vivek_dwivedi:
20180628 16:01:25
Did it using bitset ! Happy coding ! 

aexpo:
20170728 15:13:18
You can try this case:


Petar Bosnjak:
20150201 23:50:15
Last edit: 20150202 15:16:32 

Shashank Garg:
20140906 19:36:24
Last edit: 20140910 12:45:31 

Mukesh Yadav:
20121128 17:48:46
finally ... but cost a lot of time coz of wrong assumption , I shd start looking quess much more carefully from now :(P)


Suresh Iyengar:
20110624 15:40:54
Any hints to solve this problem?


Gurpreet Singh:
20110616 18:38:46
Not exactly same but very similar to : http://www.codechef.com/problems/TEAMSEL/

Added by:  Lawl 
Date:  20110616 
Time limit:  1s2.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own problem 