Splitting the Loot Evenly

MediumDynamic-ProgrammingSubset-SumDecisionArrays6 hidden tests

You are given n positive integers. Decide whether they can be divided into two groups so that every value goes into exactly one group and the two groups have equal total sums.

Input format

Line 1: an integer n, the count of values. Line 2: n space-separated positive integers.

Output format

A single line: YES if such a split exists, otherwise NO.

Constraints

1 <= n <= 200
1 <= each value <= 1000

Examples

Example 1

Input

4
1 5 11 5

Expected

YES

Explanation

Total is 22, so each half must sum to 11. The group {11} and the group {1,5,5} both sum to 11, so the answer is YES.

Example 2

Input

3
1 2 5

Expected

NO

Explanation

Total is 8, so each half would need to sum to 4, but no subset of {1,2,5} sums to 4, so the answer is NO.

Ready to solve this?

Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.

Sign in to solve →