Determine whether or not can an array of numbers can be divided into two arrays, with each array holding the same sum of numbers

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

The two for-loops are for weighing the two parts of the array, to find the array balancing point of an array.

Think of it like this:

You have a empty balance scale, in the first iteration of the outer for loop, i is zero.

It comes to first for loop, here j is 0 and i is 0 i < j is false, so it doesn't enter the first for-loop and it goes into the second for-loop and subtracts all the numbers from sum.

From second iteration onwards of the outer for-loop, it starts entering the first for-loop and starts adding the elements of the array one-by-one to the sum.

In pictures, it is like starting with an empty balance scale, adding all the elements into the second scale, and moving one by one element to the first scale, like this:

In the end, if the sum is zero, then the array can be balanced, so return true. If the sum isn't 0, it's unbalanced.

The values in the are balanced by the loops like this:

Iteration of outer for loop when i is 0
Loop 2 -> i(0) j(0) Subtract 1, sum is -1
Loop 2 -> i(0) j(1) Subtract 3, sum is -4
Loop 2 -> i(0) j(2) Subtract 2, sum is -6
Loop 2 -> i(0) j(3) Subtract 6, sum is -12

Iteration of outer for loop when i is 1
Loop 1 -> i(1) j(0) Add 1, sum is 1
Loop 2 -> i(1) j(1) Subtract 3, sum is -2
Loop 2 -> i(1) j(2) Subtract 2, sum is -4
Loop 2 -> i(1) j(3) Subtract 6, sum is -10

Iteration of outer for loop when i is 2
Loop 1 -> i(2) j(0) Add 1, sum is 1
Loop 1 -> i(2) j(1) Add 3, sum is 4
Loop 2 -> i(2) j(2) Subtract 2, sum is 2
Loop 2 -> i(2) j(3) Subtract 6, sum is -4

Iteration of outer for loop when i is 3
Loop 1 -> i(3) j(0) Add 1, sum is 1
Loop 1 -> i(3) j(1) Add 3, sum is 4
Loop 1 -> i(3) j(2) Add 2, sum is 6
Loop 2 -> i(3) j(3) Subtract 6, sum is 0

Final result is true, therefore the array can be balanced

Code:

public class Test {

    public static void main(String[] args) {
        int[] test = { 1, 3, 2, 6 };
        System.out.println("\nFinal result is "+canBalance(test));
    }

    public static boolean canBalance(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            System.out.println("\nIteration of outer for loop when i is " + i);
            int sum = 0;
            for (int j = 0; j < i; j++){
                sum += nums[j];
                System.out.println("Loop 1 -> i(" +i + ") j("+j + ") Add "+nums[j] + ", sum is "+sum+"       ");
            }
            for (int j = i; j < nums.length; j++){
                sum -= nums[j];
                System.out.println("Loop 2 -> i(" +i + ") j("+j + ") Subtract "+nums[j] + ", sum is "+sum+"       ");
            }
            if (sum == 0)
                return true;
        }
        return false;
    }
}

---

If you want to allow shuffling between the elements of the array, you can use recursion as follows (comments are self-explanatory)

public class Test {

    public static void main(String[] args) {
        int[] original = { 10, 2, 24, 32 };
        System.out.println(canDivideArray(original));
    }

    private static boolean canDivideArray(int[] originalArray) {
        int total = 0;

        for (int number : originalArray) {
            total += number;
        }

        // check if sum == 2x for any value of x
        if (total % 2 != 0) {
            return false;
        } else {
            // sum of each half array should be x
            total /= 2;
        }
        return isTotal(originalArray, originalArray.length, total);
    }

    private static boolean isTotal(int array[], int n, int total) {
        // successful termination condition
        if (total == 0) {
            return true;
        }
        
        // unsuccessful termination when elements have finished but total is not reached
        if (n == 0 && total != 0){
            return false;
        }

        // When last element is greater than total
        if (array[n - 1] > total)
            return isTotal(array, n - 1, total);

        //check if total can be obtained excluding the last element or including the last element 
        return isTotal(array, n - 1, total - array[n - 1]) || isTotal(array, n - 1, total); 
    }

}

Answer 2

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 3

This is a recursive solution to the problem, one non recursive solution could use a helper method to get the sum of indexes 0 to a current index in a for loop and another one could get the sum of all the elements from the same current index to the end, which works. Now if you wanted to get the elements into an array and compare the sum, first find the point (index) which marks the spilt where both side's sum are equal, then get a list and add the values before that index and another list to go after that index.

Here's mine (recursion), which only determines if there is a place to split the array so that the sum of the numbers on one side is equal to the sum of the numbers on the other side. Worry about indexOutOfBounds, which can easily happen in recursion, a slight mistake could prove fatal and yield a lot of exceptions and errors.

public boolean canBalance(int[] nums) {
  return (nums.length <= 1) ? false : canBalanceRecur(nums, 0);   
}
public boolean canBalanceRecur(int[] nums, int index){ //recursive version
  if(index == nums.length - 1 && recurSumBeforeIndex(nums, 0, index) 
  != sumAfterIndex(nums, index)){ //if we get here and its still bad
  return false;
  }
  if(recurSumBeforeIndex(nums, 0, index + 1) == sumAfterIndex(nums, index + 1)){
  return true;
  }
  return canBalanceRecur(nums, index + 1); //move the index up
}
public int recurSumBeforeIndex(int[] nums, int start, int index){
   return (start == index - 1 && start < nums.length) 
   ? nums[start] 
   : nums[start] + recurSumBeforeIndex(nums, start + 1, index);
}

public int sumAfterIndex(int[] nums, int startIndex){
  return (startIndex == nums.length - 1) 
  ? nums[nums.length - 1] 
  : nums[startIndex] + sumAfterIndex(nums, startIndex + 1);
}

//non recursively

public boolean canBalance(int[] nums) {
   for(int a = 0; a < nums.length; a++) {
      int leftSum = 0;
      int rightSum = 0; 
      for(int b = 0; b < a; b++) {
      leftSum += nums[b];
      }
      for(int c = a; c < nums.length; c++) {
      rightSum += nums[c];
      }
      if(leftSum == rightSum) {
      return true;
      }
   }
   return false;
}