Given an array containing N numbers, we need to split the array into two subsets, such that each subset contains N/2 numbers, and the difference between the sum of the two subsets is minimised. I was able to come up with this : asked 23 Aug '17, 00:43

Sort array in decreasing order. create 2 array of n/2 max size. insert element into those array using below condition.
for maximum cases it will give you correct result and for other will give close result. Another method is to try for all possible combination which is, of course, very slow. answered 03 Apr, 17:21

let S be the sum of the N numbers. You want to get as close as possible to S/2 Now let A[i][j] = 1 if you can get the sum j using the first i elements, 0 otherwise A[i][j] = A[i1][je[i]] or A[i1][j] You can even reduce the space to only using the last 2 lines. If you need to optimize further, note that not all the j values are reachable. So you can build the solution using a DFS style approach with memorization so that you only explore the "1" states. answered 23 Aug '17, 08:40

did you check out this geeksforgeeks link? This has two solution O(n^2) and O(n*sum of all elements). hope you find them of any value. PS : I'm also trying to understand, If I was able to figure out certainly I'll try to help you out. answered 23 Aug '17, 19:55
1
That's a $\mathcal{O}(2^n)$ solution on the geeksforgeeks page, and not $\mathcal{O}(n^2)$, otherwise the author would have proved that P=NP! The second thing is that the article is about the standard partition problem which does not have any restriction on the size of the two subsets, whereas here they must be of size N/2.
(23 Aug '17, 21:35)

It may be done like this each time either pick the element or not and do this until you have N/2 elements and when you have picked N/2 elements then do this ans = min( ans, (sum_of_N_elems  sum_of_cur_N/2_elems) ). With this method you have to traverse many paths and complexity will be high so you can use dynamic programming to reduce complexity. answered 26 Aug '17, 15:45

Sorry ,i know its a bit late to ask,bt can u tell the constraint for n,a[i]?(assuming a is array)
This question was asked in an interview, the interviewer didn't mention any constraints.