Question
The Two Treasure Chests
In an ancient kingdom, there once lived a wise King who loved collecting treasures. Over the years, he gathered N precious items, each worth a certain value.
One day, as the King grew old, he decided to divide his treasures between his two heirs.
But he was a fair ruler — he wanted both chests to contain treasures of equal total value.
The royal treasurer was given a list, arr, where each entry represented the value of the treasures. His task was to find out whether it was possible to split all treasures into two groups such that the sum of values in both groups was exactly equal.
Input
The first line of input contains an integer N, representing the number of elements in the array arr.
The second and final line of input contains N space-separated integers, representing the elements of the array arr.
The second and final line of input contains N space-separated integers, representing the elements of the array arr.
Output
Print "True" if the given array can be partitioned into two subsets with equal sum; otherwise, print "False" (without quotes).
Example
Input
4
1 12 5 6
Output
True
Explanation
The given array can be divided into two subsets: [1, 5, 6] and [12], both having a sum of 12.
Input
4
1 12 5 7
Output
False
Explanation
The sum of the elements in the array 1 + 12 + 5 + 7 = 25 is odd. Therefore, the given array cannot be partitioned into two subsets with equal sum.
Input
3
1 3 6
Output
False
Explanation
There is no possible way to partition the given array into two subsets with equal sum because the single element 6 is greater than half of the total sum of the array elements (1 + 3 + 6 = 10).
4
1 12 5 6
Output
True
Explanation
The given array can be divided into two subsets: [1, 5, 6] and [12], both having a sum of 12.
Input
4
1 12 5 7
Output
False
Explanation
The sum of the elements in the array 1 + 12 + 5 + 7 = 25 is odd. Therefore, the given array cannot be partitioned into two subsets with equal sum.
Input
3
1 3 6
Output
False
Explanation
There is no possible way to partition the given array into two subsets with equal sum because the single element 6 is greater than half of the total sum of the array elements (1 + 3 + 6 = 10).