How to optimally divide an array into two subarrays so that sum of elements in both are same, otherwise give an error?

There exists a solution, which involves dynamic programming, that runs in O(n*TotalSum), where n is the number of elements in the array and TotalSum is their total sum.

The first part consists in calculating the set of all numbers that can be created by adding elements to the array.

For an array of size n, we will call this T(n),

T(n) = T(n-1) UNION { Array[n]+k | k is in T(n-1) }

(The proof of correctness is by induction, as in most cases of recursive functions.)

Also, remember for each cell in the dynamic matrix, the elements that were added in order to create it.

Simple complexity analysis will show that this is done in O(n*TotalSum).

After calculating T(n), search the set for an element exactly the size of TotalSum / 2.

If such an item exists, then the elements that created it, added together, equal TotalSum / 2, and the elements that were not part of its creation also equal TotalSum / 2 (TotalSum - TotalSum / 2 = TotalSum / 2).

This is a pseudo-polynomial solution. AFAIK, this problem is not known to be in P.

This is called partition problem. There are optimal solutions for some special cases. However, in general, it is an NP-complete problem.

In its common variant, this problem imposes 2 constraints and it can be done in an easier way.

1. If the partition can only be done somewhere along the length of the array (we do not consider elements out of order)
2. There are no negative numbers.

The algorithm that then works could be:

1. Have 2 variables, leftSum and rightSum
2. Start incrementing leftSum from the left, and rightSum from the right of the array.
3. Try to correct any imbalance in it.

The following code does the above:

public boolean canBalance(int[] nums) {  int leftSum = 0, rightSum = 0, i, j;  if(nums.length == 1)      return false;  for(i=0, j=nums.length-1; i<=j ;){      if(leftSum <= rightSum){         leftSum+=nums[i];         i++;      }else{         rightSum+=nums[j];         j--;      }  }  return (rightSum == leftSum);}

The output:

canBalance({1, 1, 1, 2, 1})       → true    OK      canBalance({2, 1, 1, 2, 1})       → false   OK      canBalance({10, 10})              → true    OK          canBalance({1, 1, 1, 1, 4})       → true    OK      canBalance({2, 1, 1, 1, 4})       → false   OK      canBalance({2, 3, 4, 1, 2})       → false   OK      canBalance({1, 2, 3, 1, 0, 2, 3}) → true    OK      canBalance({1, 2, 3, 1, 0, 1, 3}) → false   OK      canBalance({1})                   → false   OK      canBalance({1, 1, 1, 2, 1})       → true    OK

Ofcourse, if the elements can be combined out-of-order, it does turn into the partition problem with all its complexity.