I have a problem where I read in a 2D matrix and divide the matrix into 2 parts, where the sums of each part are equal. Each part must contain contiguous integers that can be networked together by following paths from one intger containing cell to another via shared sides. The first matrix is:

4 4
50 85 9 33
301 46 40 19
105 29 11 12
20 13 23 16

The solution is:

301 + 105 = 406
50 + 85 + 9 + 33 + 46 + 40 + 19 + 20 + 29 + 11 + 12 + 13 + 23 + 16 = 406

I get the matrix read in and I added up all of the numbers and divided by 2. This gives me the total that each part should be equal to. Does anyone know how I should attempt to figure out which numbers I should try to add up in the array to get the correct total? I am at a loss there. Thanks for any input.

Can you explain more of "shared side" . Does it include diagonal numbers. The problem was simpler if I could simply think of as an array of number of which I had to divide in 2 sets whose sum was equal.
Also I have following questions
1) A solution will not be possible if the sum of matrix is odd
2) I assume the numbers in the matrix to be natural numbers
3) can 2 elements of matrix be equal ?

No, the shared sides would not be diagonal. The best way I know to describe it is that the element would have a shared side by going side to side through the elements or up and down through the elements. So, for example,

M[1][1] would share a side with M[0][0], M[1][2], and M[2][1] but not with M[0][1] or M[2][2].

I assume there would not be a solution if the sum of the elements are odd because the 2 parts would not be equal. All of the numbers are regular integers. And I also assume that 2 elements can be equal. The data file has an unlimited number of matrices in it but they are defined like in the original message above. Thanks.

This article has been dead for over six months. Start a new discussion instead.