Equal Subset Sum Partition

You are given a list of integers. Your task is to determine whether the list can be partitioned into two subsets such that the sum of the elements in both subsets is equal.

Formally, let the array be arr of size n and let its total sum be \(S = \sum_{i=1}^{n} arr[i]\). The problem is to decide if there exists a subset of arr whose sum equals \(\frac{S}{2}\). Note that if \(S\) is odd, then an equal partition is impossible.

The expected output is Possible if such a partition exists, and Not Possible otherwise.

inputFormat

The input is provided via stdin in the following format:

n
arr[0] arr[1] ... arr[n-1]

Here, n is the number of elements, and the next line contains n space-separated integers. In the case where n = 0, the array is empty and should be considered as already partitionable into two empty subsets.

outputFormat

Print the string Possible if the array can be partitioned into two subsets with equal sum, or Not Possible otherwise. The output should be sent to stdout without any extra characters.

4
1 5 11 5

Possible