You are not logged in. Please login at to post your questions!


Split array into two subsets with minimum difference

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 :

A[i][j][k] = 1 if there is a subset of size 'k' of the first 'i' elements that has sum 'j'. Fill this, and then check A[N][j][N/2] for all j and pick whichever minimises the difference. I want to know if there is a faster way of doing this.

asked 23 Aug '17, 00:43

hemanth_1's gravatar image

accept rate: 26%

Sorry ,i know its a bit late to ask,bt can u tell the constraint for n,a[i]?(assuming a is array)

(03 Apr, 19:25) vivek_19982996★

This question was asked in an interview, the interviewer didn't mention any constraints.

(11 Apr, 23:44) hemanth_16★

Sort array in decreasing order. create 2 array of n/2 max size. insert element into those array using below condition.

for element in array:
    if sum(array1)<=sum(array2):
        if array1 is not full:
        if array2 is not full:

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

surya_singh_'s gravatar image

accept rate: 0%

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[i-1][j-e[i]] or A[i-1][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

coding_pill's gravatar image

accept rate: 0%

I think a greedy approach might work, though I dont know any proof. Start picking elements one by one. Keep track of the difference sum sa, sb for 2 sets A and B. Now put a element in first set if it minimizes |sa-sb| else put it in the other set.


answered 23 Aug '17, 14:55

rajarshi_basu's gravatar image

accept rate: 10%


That would probably give different solutions for different orderings of the input array. I tried taking the numbers in the sorted order and then doing exactly what you mentioned, but it doesn't work (try {1,2,3,4} as the input) :/ what seems to be minimising the difference at some point might not be optimal overall.

(23 Aug '17, 18:52) hemanth_16★

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

sandeep_007's gravatar image

accept rate: 15%


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) meooow ♦6★

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

visha_l's gravatar image

accept rate: 0%

edited 26 Aug '17, 15:48

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 23 Aug '17, 00:43

question was seen: 933 times

last updated: 11 Apr, 23:44