Split an even-size array into two sets of equal length and equal sum of their elements.

general
1

There was a weekly challenge question on TECHGIG. Question was something like-"
There is an array of odd size (size<100000). You have to remove any one element from the array, so that array becomes even in size. Now check whether, it is possible to divide the even size array into two equal size set so that total sum of the elements of each set is same. Return 1 if it is possible, otherwise return -1".

How to approach this question? Since size of array was quite large, so, using Dp approach just like “subset sum problem” (having time complexity O(sum*sizeof_array)) seemed to be quite expensive.

2

Can you please provide exact problem statement? I believe you are missing something quite important here with your description of the problem. In general, task which you described is most likely unsolvable. One can show that being able to solve it for array of doubles / array of intergers upto 1e18 means being able to solve 0/1 knapsack problem which is NP.

However, it may get completely different after taking something specific about problem into account. Like it may turn out that constraints on numbers are very small, or something like that.