Submit | All submissions | Best solutions | Back to list |

## HS11PART - Half of a Set |

You are given *X*, a set of *n* < 20 positive integers: *x _{1}*,

*x*, ...

_{2}*x*, where

_{n}*x*< 20. Let

_{i}*S*=

*x*+

_{1}*x*+ ... +

_{2}*x*be the sum of all

_{n}*x*. Please, check if there exists a subset of

_{i}*X*whose sum of elements is equal to

*S*/2.

### Input

First `t < 500`, the nuber of sets. Next, for each test case, two lines follow. The first contains ` n`, while the second the

`set elements, separated by spaces.`

*n*### Output

For each test case output one word in a separate line: `YES` if it is possible to achieve *S*/2 and `NO` if it is impossible.

### Example

Input:4 3 2 1 3 3 11 10 9 4 1 2 1 6 5 11 1 2 10 18Output:YES NO NO YESComment:1: 2 + 1 = 3 2: no solution 3: no solution 4: 11 + 10 = 1 + 2 + 18

### Scoring

By solving this problem you score 10 points.

Added by: | kuszi |

Date: | 2012-01-17 |

Time limit: | 0.585s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM32-GCC ASM64 GAWK MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET |

Resource: | High School Programming League |