Determine whether or not can an array of numbers c

问题:

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

回答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); 
    }

}

回答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;
}

回答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;
}

回答4:

I guess 'dividing' in the original question does not allow re-ordering of the array. So, you simply break the array at a particular position, and we will have the left side and the right side of the array. Numbers in each side should have the same sum.

The index (i) of outer loop is the breaking position.

for (int i = 0; i < nums.length; i++) {

The first inner loop sums the left side of the array.

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

The second inner loop subtracts elements of the right side from the sum of the left array.

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

If the final result is zero, it means the sum of left side and right side is the same. Otherwise, continue the outer loop and examine other breaking position until we find the right breaking position.

回答5:

Approaching this problem with DP solution.

//Create a 2D array and fill in bottom up manner //DP[totalsum / 2 + 1] [ length of array + ]

bool divisible(int arr[], int size)
{
int sum = 0;

// Determine the sum 
for (i = 0; i < size; i++) sum += arr[i];

if (sum%2 != 0) return false;

bool DP[sum/2+1][size+1];

// initialize top row as true
for (i = 0; i <= size; i++)
    DP[0][i] = true;

// initialize leftmost column, except DP[0][0], as 0
for (i = 1; i <= sum/2; i++)
    DP[i][0] = false;     

 // Fill the partition table in botton up manner 
 for (int i = 1; i <= sum/2; i++)  
 {
     for (int j = 1; j <= size; j++)  
     {
         DP[i][j] = DP[i][j-1];
         if (i >= arr[j-1])
             DP[i][j] = DP[i][j] || DP[i - arr[j-1]][j-1];
     }        
 }    
 return DP[sum/2][size];
}     

回答6:

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

回答7:

I wrote a standalone method to sum parts of an array and used this in my solution to get the simplest method I can see possible. If anyone has any comments, please join in. I appreciate the comments.

//Create a method that gets the sum from start to the iteration before end.
public int sumArray (int[] nums, int start, int end)
{
  //Create a sum int that tracks the sum.
  int returnSum = 0;
  //Add the values from start (inclusive) to end (exclusive). In other words i : [start, end)
  for (int i = start; i < end; i++)
  {
    returnSum += nums[i];
  }
  return returnSum;
}

//This is our main class.
public boolean canBalance(int[] nums) {
  //If nums has an actual value, we can work with it.
  if (nums.length > 0)
  {
    //We check to see if there is a value that is equal by using the sumArray method.
    for (int i = 0; i < nums.length; i++)
    {
      //If from [0,i) the value equals from [i, nums.length), we return true;
      if (sumArray(nums, 0, i) == sumArray(nums, i, nums.length))
      {
        return true;
      }
    }
    //If we finish the loop, and find nothing, we return false;
    return false;
  }
  //If there is no value, we return false.
  else
  {
    return false;
  }
}

回答8:

When there aren't any curly braces around around code after a for statement in Java, the very next line is the only line processed as part of the for statement. In this case, the for is like a function that calls the next line of code, which is a for statement that then calls the next line of code. So the first for calls the second for which evaluates to see if the two sides are the same, and if they aren't then it kicks back up to the second for which continues incrementing itself until it finishes and then it returns to the first for, which increments, and calls the second for... and so on. That code seems like it's partially broken, though, since it would have to have all numbers in numeric order, and it doesn't check anything in the middle.

For instance:
{1, 2, 3, 1} //evaluates to true because 1-1=0, although it should be false
{6, 2, 2, 3} //evaluates to true because 6-3-2=0, although it should be false
{2, 3, 4, 6} //evaluates to true because 2+3-6=0, although it should be false