Divide Array into 2 equal sum parts using only one loop, need alternative approach

Question

Usually what we do is 1.we calculate sum of whole array from left and call it Leftsum 2.then we starts traversing array from Right end and start adding every element into RIGHTSUM, and subracting every element from LEFTSUM 3. untill LEFTSUM=RIGHTSUM,then we assign current value of iterator variable I to splitpoint 4.Now array before SPLITPOINT index and from SPLITPOINT index to end have equal sum

MAIN PROBLEM------>

but this will work if array is ((3 , 5 , 10) , (3, 10 , 5)) but not on (3 , 5 , 5 , 3, 10 , 10) because we cannot find SPLITPOINT here whose left and right array sum is equal

answer of second part should also be (3,5,10) (5,3,10) Again sum of 2 parts should be equal not length this is an easy illustation example above

In general it's not possible to partition an array into two parts with an equal sum. Is such a partition guaranteed to exist in your case? Why? — Joe Halliwell, Nov 28 '19 at 09:32
that's basic things that array elements will be entered in such a manner that 2 equal sum with using these array elements are possible consider my second example (3 , 5 , 5 , 3, 10 , 10) yes obviously programm will print not possible if array element's sum cannot be divided into 2 equal sums — Umesh Pathak, Nov 28 '19 at 09:46
so for what purpose u want to divide the array?can u explain that@Umesh Pathak — Sandhiya, Nov 28 '19 at 09:54
@sandhiya Just a competitive programming question asked in interviews — Umesh Pathak, Nov 28 '19 at 11:09

score 1 · Answer 1 · answered Nov 28 '19 at 09:54

Suppose the total for the whole sequence is N. You're effectively looking for a sub-sequence that sums to N/2. (Note: if N is odd, there is no such sub-sequence!)

This is the "subset sum" problem. There's a decent Java solution for that at Finding all possible combinations of numbers to reach a given sum.

Divide Array into 2 equal sum parts using only one loop, need alternative approach

1 Answers1