Equal Sum Partitioning

Given an array of positive integers, determine whether it can be partitioned into two subsets whose sums are equal. Formally, for an array \(A = [a_1, a_2, \dots, a_n]\), check if there exist two disjoint subsets \(S_1\) and \(S_2\) such that:

\(\sum_{x \in S_1} x = \sum_{x \in S_2} x\).

If such a partition exists, output True; otherwise, output False.

inputFormat

The input is given via stdin. The first line contains a single integer (n) (1 ≤ n ≤ 1000) denoting the number of elements in the array. The second line contains (n) space-separated positive integers (each not exceeding 10^5).

outputFormat

Print True if the array can be partitioned into two subsets with equal sum, otherwise print False.## sample

4
1 5 11 5

True