TUG - Tug of War

no tags 

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
kuderrahul: 2023-03-24 09:13:04

deceiving constraints

Last edit: 2023-03-24 09:15:38
shimul58: 2021-09-06 01:25:29

pigeonhole principle && dp

yfsyfs: 2020-03-15 17:25:37

knapsack seems does not work~ multiple knapsack with any optimate

anirudnits: 2018-12-31 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: 2018-12-31 17:00:04
vivek_dwivedi: 2018-06-28 16:01:25

Did it using bitset ! Happy coding !

aexpo: 2017-07-28 15:13:18

You can try this case:
1
5
2 50 60 53 57
At least in my approach this case proved to be a tricky one at the cost of 1 WA

Last edit: 2017-07-28 15:14:41
Mukesh Yadav: 2012-11-28 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)

Last edit: 2012-11-28 17:50:05
Suresh Iyengar: 2011-06-24 15:40:54

Any hints to solve this problem?

To be solved like knapsack?

Answer: this problem can be solved either by dp or a mathematical observation.

Last edit: 2011-06-24 22:43:54
Gurpreet Singh: 2011-06-16 18:38:46

Not exactly same but very similar to : http://www.codechef.com/problems/TEAMSEL/

RE:Though it sounds same but this one is very very easy.....

Last edit: 2011-06-16 19:35:26

Added by:Lawl
Date:2011-06-16
Time limit:1s-2.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem