Determine whether or not can an array of numbers c

Question

Below is a code to determine whether or not can an array of numbers can be divided into two arrays, with each array holding the same sum of numbers. for example: {1, 3 ,2, 6} can be divided into {6} and {1,2,3}, therefore return true while {1,5,7} can't be divided into two, balanced array, therefore return false

public boolean canBalance(int[] nums) {
    for (int i = 0; i < nums.length; i++) { 
       int sum = 0;
       for (int j = 0; j < i; j++) sum += nums[j];
       for (int j = i; j < nums.length; j++) sum -= nums[j];
       if (sum == 0) return true;    
    }    
    return false;
}

it's an accepted answer for an exercise in codingbat, I don't understand this piece in particular:

for (int j = 0; j < i; j++) sum += nums[j];
for (int j = i; j < nums.length; j++) sum -= nums[j];

doesn't for iteration usually starts with { and ends with } ? and how come if sum == 0 means it can be balanced? I have tried noting it down on piece of paper with array of {1,3,2,6} and had sum of 26, which returns false, where it's obvious that {1,3,2,6} should return true.

I think I misread the code, I don't know which, though. Or maybe the algorithm is false, but it was accepted in codingbat

Answer 1

If reordering of the elements of the array is not allowed, we just have to find the split point in the given array. The solution in the question does this by trying all possible split points and checking if the sum of the two parts is equal. It has effort that is quadratic in the length of the input array.

Note that it is easy to come up with solutions that have linear effort, for example the following snippet. It builds sums of the elements on the left side and on the right side of array, in each step the smaller sum is increased by adding an array element. This is repeated until the parts meet.

This assumes that the array does not contain any negative numbers.

public boolean canBalance(int[] nums) {
  int sumL = 0, sumR = 0;
  int l = -1, r = nums.length;
  while (r - l > 1) {
    if (sumL < sumR) {
      sumL += nums[++l];
    } else {
      sumR += nums[--r];
    }
  }
  return sumL == sumR;
}

Answer 2

Just as @Alvin Bunk said in the comment, the answer you give in the question itself is not a good answer, it works differently even if the order of elements is changed in the array.

You should check this wiki for the theory & implement it: http://en.wikipedia.org/wiki/Partition_problem