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

Question

Below is the code to determine whether an array of numbers can be divided into two arrays, with each array containing the same sum of numbers. for example: {1, 3, 2, 6} can be divided into {6} and {1,2,3}, therefore we return true while {1,5,7} cannot be divided into two balanced arrays, therefore we 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; } 

this is an accepted answer for an exercise in coding, I don't understand this fragment 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 iteration usually start with {and end with}? and how does it turn out if the sum == 0 means that it can be balanced? I tried to mark it on a piece of paper with an array of {1,3,2,6} and had a sum of 26 that returns false, where it is obvious that {1,3,2,6} should return true.

I think I read the code incorrectly, but I don’t know what. Or maybe the algorithm is false, but it was adopted in bat coding

Answer 1

Two for-loops are designed to weigh two parts of an array in order to find an array array array.

Think of it this way:

You have an empty balance scale, in the first iteration of the outer loop, I am zero.

It comes to the first for the loop, here j is 0 and I is 0 i < j false, so it does not enter the first for loop and does not go into the second for loop and does not subtract all numbers from the sum.

Starting from the second iteration of the outer for loop, it begins to introduce the first for loop and begins to add the elements of the array one by one to the sum.

In paintings, it looks like an empty balance scale, adding all the elements to the second scale and moving one element to the first scale, for example:

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

The values ​​in are balanced by such loops:

Iterate external to the loop when i equals 0
Loop 2 → i (0) j (0) Subtract 1, the sum is -1 Loop 2 → i (0) j (1) Subtract 3, the sum is -4 Loop 2 → i (0) j (2) Subtraction 2, amount -6
Loop 2 → i (0) j (3) Subtract 6, the sum is -12

Iterate external to the loop when i equals 1
Loop 1 → i (1) j (0) Add 1, sum 1 Loop 2 → i (1) j (1) Subtract 3, the sum is -2
Loop 2 → i (1) j (2) Subtract 2, the sum is -4
Loop 2 → i (1) j (3) Subtract 6, the sum is -10

Iterate external to the loop when I equals 2
Loop 1 → i (2) j (0) Add 1, sum 1 Loop 1 → i (2) j (1) Add 3, sum 4
Loop 2 → i (2) j (2) Subtract 2, the sum is 2 Loop 2 → i (2) j (3) Subtract 6, the sum is -4

Iterate external to the loop when I equals 3
Loop 1 → i (3) j (0) Add 1, the sum is 1
Loop 1 → i (3) j (1) Add 3, sum 4
Loop 1 → i (3) j (2) Add 2, the sum is 6
Loop 2 → i (3) j (3) Subtract 6, the sum is 0

The end result is correct, so the array can be balanced

the 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 array elements, 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 the elements of an array is unacceptable, we just need to find the split point in the given array. The solution in the question does this, using all possible separation points and checking if the sum of the two parts is equal. It has a force quadratic in the length of the input array.

Note that it is easy to find linear force solutions, such as the following snippet. It builds the sums of elements on the left and right of the array, at each step the smaller amount is increased by adding an array element. This is repeated until the details match.

This assumes 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 can use a helper method to get the sum of indices 0 to the current index in the for loop, and the other can get the sum of all elements from the same current index to the end, which works. Now, if you want to get the elements into an array and compare the sum, first find the point (index) that marks the spill, where both side sums are equal, then get a list and add values ​​before this index and the other list after this index.

Here's mine (recursion), which only determines if there is room for partitioning 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 small mistake can prove fatal and give 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); } 

// not 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; } 

Answer 4

I think the “division” in the original question does not allow reordering the array. Thus, you simply split the array into a specific position, and we will have the left and right parts of the array. The numbers on each side should have the same amount.

The outer contour index (i) is a violation 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 the 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, this means that the sum of the left and right sides is the same. Otherwise, continue the outer cycle and examine the other opening position until you find the correct fault position.

Answer 5

This problem is getting closer to the DP solution.

// Create a 2D array and fill it from the bottom up // DP [totalsum / 2 + 1] [array length +]

 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]; } 

Answer 6

As in @Alvin Bunk mentioned in the comment, the answer you ask in the question itself is not a good answer, it works differently, even if the order of the elements changes in the array.

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

Answer 7

I wrote a stand-alone method for summing the parts of an array and used it in my solution to get the simplest method that I see possible. If anyone has any comments, join us. 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; } } 

Answer 8

When there are no curly braces around the for statement in Java, the next line is the only line processed as part of the for statement. In this case, the for value is similar to a function that calls the next line of code, which is a for statement, which then calls the next line of code. Thus, the first for calls is the second, for which it is evaluated whether both sides will be the same, and if not, it returns to the second, for which it continues to increase until it completes, and then it returns to the first for, which increases and calls second for ... and so on. However, this code seems to be partially broken, because it should have all numbers in numerical order and not check anything in between.

For example:
{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