Please help!!!.. I am trying to solve this question:-
Divide the array into 3 subsets such that if a is the sum of elements in first subset , b is the sum of elements in second subset and c is the sum in case of third subset, then find minimum possible value of abs(a-b)+abs(b-c)+abs(c-a) …I tried using all possible combinations i.e. all possible subsets… And this approach times out. pls help in solving it in a better way.
The question does not say that you have to break into equal sub arrrays. That makes it a bit easier. Just see if the total sum (T) is divisible by 3. If yes, then just start picking the elements whose sum would be T/3 and create 3 such arrays. If not then give the remainder to any of the array.
Take care of the corner cases such as one number is itself more than T/3 or the numbers are such that they wont add upto T/3 exactly, then just settle for the nearest number. Eg. 1,2,3 Here you would have to settle for 1 and 3. Only 2 would be T/3.