Problem Statement

Fox Ciel just returned home from her trip to New Fox City. She has brought a bunch of souvenirs. You are given their values in a vector <int> value.  Now she wants to give each souvenir either to her mother or to her father. She would like to divide the souvenirs in a fair way. More precisely:
The total number of souvenirs given to her mother must be the same as the total number of souvenirs given to her father.
At the same time, the total value of souvenirs given to her mother must be the same as the total value of souvenirs given to her father.
  Return "Possible" if she can reach her goal, and "Impossible" otherwise.
Definition

Class:
FoxAndSouvenirTheNext

Method signature:
string ableToSplit(vector <int> value)

Limits

Time limit (s):
2.000
Memory limit (MB):
256
Stack limit (MB):
256
Constraints
-
value will contain between 1 and 50 elements, inclusive.
-
Each element in value will be between 1 and 50, inclusive.
Examples
0)


{1,2,3,4}
Returns: "Possible"
One valid solution is to give the souvenirs with values 1 and 4 to her mother and the other two to her father. Each parent receives two souvenirs, and as 1+4 = 2+3, the total value is also the same for both parents.
1)


{1,1,1,3}
Returns: "Impossible"
There is no valid solution. Note that {1,1,1} and {3} is not a valid way to split the souvenirs: even though the total value is the same, the number of souvenirs is not.
2)


{1,1,2,3,5,8}
Returns: "Possible"
We have 1+1+8 = 2+3+5.
3)


{2,3,5,7,11,13}
Returns: "Impossible"
The sum of values is an odd number, so it is impossible.
4)


{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48}
Returns: "Possible"

5)


{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50}
Returns: "Impossible"