Partition Equal Subset Sum

Problem statement

A relief center has packages with positive weights and wants to divide all packages between two vehicles so that their loads are equal. A package cannot be split or assigned to both vehicles. Your task Determine whether the array can be partitioned into two subsets with equal sum, using every element exactly once. Important details The subsets need not be contiguous and may preserve no particular ordering. An odd total immediately prevents an equal split. Equal package weights are still separate packages. The task is feasibility, not printing a partition. Worked example For [1, 5, 11, 5], one vehicle takes 11 and the other takes 1 + 5 + 5. Both loads are 11, so the answer is true.

Input format

The first line contains n. The next line contains n space-separated integers; for n = 0 this line may be empty.

Output format

Print true if the condition holds, otherwise false.

Constraints

1 <= n <= 200; 1 <= values <= 100.

Sample input

4
1 5 11 5

Sample output

true