How to optimally split an array into two subarrays so that the sum of the elements in both is the same, otherwise it gives an error?

Question

How to optimally split an array into two subarrays so that the sum of the elements in both subarrays is the same, otherwise it produces an error?

Example 1

Given an array

10, 20 , 30 , 5 , 40 , 50 , 40 , 15 

It can be shared as

 10, 20, 30, 5, 40 

as well as

 50, 40, 15 

Each subarray sums up to 105.

Example 2

 10, 20, 30, 5, 40, 50, 40, 10 

An array cannot be divided into 2 arrays of equal sum.

Answer 1

 public class Problem1 { public static void main(String[] args) throws IOException{ Scanner scanner=new Scanner(System.in); ArrayList<Integer> array=new ArrayList<Integer>(); int cases; System.out.println("Enter the test cases"); cases=scanner.nextInt(); for(int i=0;i<cases;i++){ int size; size=scanner.nextInt(); System.out.println("Enter the Initial array size : "); for(int j=0;j<size;j++){ System.out.println("Enter elements in the array"); int element; element=scanner.nextInt(); array.add(element); } } if(validate(array)){ System.out.println("Array can be Partitioned");} else{ System.out.println("Error");} } public static boolean validate(ArrayList<Integer> array){ boolean flag=false; Collections.sort(array); System.out.println(array); int index=array.size(); ArrayList<Integer> sub1=new ArrayList<Integer>(); ArrayList<Integer> sub2=new ArrayList<Integer>(); sub1.add(array.get(index-1)); array.remove(index-1); index=array.size(); sub2.add(array.get(index-1)); array.remove(index-1); while(!array.isEmpty()){ if(compareSum(sub1,sub2)){ index=array.size(); sub2.add(array.get(index-1)); array.remove(index-1); } else{ index=array.size(); sub1.add(array.get(index-1)); array.remove(index-1); } } if(sumOfArray(sub1).equals(sumOfArray(sub2))) flag=true; else flag=false; return flag; } public static Integer sumOfArray(ArrayList<Integer> array){ Iterator<Integer> it=array.iterator(); Integer sum=0; while(it.hasNext()){ sum +=it.next(); } return sum; } public static boolean compareSum(ArrayList<Integer> sub1,ArrayList<Integer> sub2){ boolean flag=false; int sum1=sumOfArray(sub1); int sum2=sumOfArray(sub2); if(sum1>sum2) flag=true; else flag=false; return flag; } } 

// Greedy approach //

Answer 2

There is a solution that includes dynamic programming, which is performed in O(n*TotalSum) , where n is the number of elements in the array, and TotalSum is their total amount.

The first part is to compute the set of all numbers that can be created by adding elements to the array.

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

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

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

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

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

After calculating T(n) find in the set the element, exactly TotalSum/2 size of TotalSum/2 .

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

This is a pseudopolynomial solution. AFAIK, this problem is not known in P.

Answer 3

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

Answer 4

In its general version, this problem imposes 2 limitations, and this can be done in a simpler way.

• If the section can only be done somewhere along the length of the array (we do not consider elements out of order)
• No negative numbers.

The algorithm, which then works, could be:

• Have 2 variables, leftSum and rightSum
• Start increasing leftSum to the left and rightSum to the right of the array.
• Try to correct any imbalance.

The following code does the following:

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

Exit:

 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 

Of course, if the elements can be combined out of order, it turns into a partition problem with all its complexity.

Answer 5

This task says that if an array can have two subarrays, their sum of elements being the same. Therefore, it is necessary to return a boolean value. I found an efficient algorithm: Algo: Procedure Step 1. Take an empty array as a container, sort the initial array and save it in an empty one. Step 2: now take two dynamically allocated arrays and select the highest and second maximum from the auxiliary array and save it in two subarrays, respectively, and delete it from the auxiliary array. Step 3. Compare the sum of the elements in the subarrays, a smaller amount will have a chance to extract the highest remaining element in the array and then remove it from the container. Step 4: Go through step 3 until the container is empty. Step 5: Compare the sum of the two subarrays if they are true true else false.

// The complexity of this problem is that many combinations are possible, but this algorithm has one unique way.

Answer 6

I was asked this question in an interview, and I gave a simple solution below, since I had not seen this problem on any website before.

Assume an array A = {45,10,10,10,10,10,5} Then the split will be equal to index = 1 (index based on 0), so that we have two equal sums {45} and {10,10,10 , 10.5}

 int leftSum = A[0], rightSum = A[A.length - 1]; int currentLeftIndex = 0; currentRightIndex = A.length - 1 

/ * Move the index pointers to the middle of the array until currentRightIndex! = CurrentLeftIndex. Increase leftIndex if the sum of the left elements is still less than or equal to the sum of the elements to the right of "rightIndex". At the end, check if there is leftSum == rightSum. If true, we got the index as currentLeftIndex + 1 (or just currentRightIndex, since currentRightIndex in this case will be equal to currentLeftIndex + 1). * /

 while (currentLeftIndex < currentRightIndex) { if ( currentLeftIndex+1 != currentRightIndex && (leftSum + A[currentLeftIndex + 1) <=currentRightSum ) { currentLeftIndex ++; leftSum = leftSum + A[currentLeftIndex]; } if ( currentRightIndex - 1 != currentLeftIndex && (rightSum + A[currentRightIndex - 1] <= currentLeftSum) { currentRightIndex --; rightSum = rightSum + A[currentRightIndex]; } } if (CurrentLeftIndex == currentRightIndex - 1 && leftSum == rightSum) PRINT("got split point at index "+currentRightIndex); 

Answer 7

@Gal Subset-Sum is NP-Complete problem and has a pseudo-polynomial dynamic programming algorithm O (n * TotalSum). But this problem is not NP-Complete. This is a special case, and in fact it can be solved in linear time.

Here we are looking for an index where we can divide the array into two parts with the same amount. Check out the following code.

Analysis: O (n), since the algorithm iterates only through the array and does not use TotalSum.

 public class EqualSumSplit { public static int solution( int[] A ) { int[] B = new int[A.length]; int[] C = new int[A.length]; int sum = 0; for (int i=0; i< A.length; i++) { sum += A[i]; B[i] = sum; // System.out.print(B[i]+" "); } // System.out.println(); sum = 0; for (int i=A.length-1; i>=0; i--) { sum += A[i]; C[i] = sum; // System.out.print(C[i]+" "); } // System.out.println(); for (int i=0; i< A.length-1; i++) { if (B[i] == C[i+1]) { System.out.println(i+" "+B[i]); return i; } } return -1; } public static void main(String args[] ) { int[] A = {-7, 1, 2, 3, -4, 3, 0}; int[] B = {10, 20 , 30 , 5 , 40 , 50 , 40 , 15}; solution(A); solution(B); } } 

Answer 8

Tried another solution. other than Wiki solutions (partition issue)

 static void subSet(int array[]) { System.out.println("Input elements :" + Arrays.toString(array)); int sum = 0; for (int element : array) { sum = sum + element; } if (sum % 2 == 1) { System.out.println("Invalid Pair"); return; } Arrays.sort(array); System.out.println("Sorted elements :" + Arrays.toString(array)); int subSum = sum / 2; int[] subSet = new int[array.length]; int tmpSum = 0; boolean isFastpath = true; int lastStopIndex = 0; for (int j = array.length - 1; j >= 0; j--) { tmpSum = tmpSum + array[j]; if (tmpSum == subSum) { // if Match found if (isFastpath) { // if no skip required and straight forward // method System.out.println("Found SubSets 0..." + (j - 1) + " and " + j + "..." + (array.length - 1)); } else { subSet[j] = array[j]; array[j] = 0; System.out.println("Found.."); System.out.println("Set 1" + Arrays.toString(subSet)); System.out.println("Set 2" + Arrays.toString(array)); } return; } else { // Either the tmpSum greater than subSum or less . // if less , just look for next item if (tmpSum < subSum && ((subSum - tmpSum) >= array[0])) { if (lastStopIndex > j && subSet[lastStopIndex] == 0) { subSet[lastStopIndex] = array[lastStopIndex]; array[lastStopIndex] = 0; } lastStopIndex = j; continue; } isFastpath = false; if (subSet[lastStopIndex] == 0) { subSet[lastStopIndex] = array[lastStopIndex]; array[lastStopIndex] = 0; } tmpSum = tmpSum - array[j]; } } } 

I have tested. (It works well with a positive number greater than 0), please let me know if someone encounters a problem.

Answer 9

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

Answer 10

Below is the working version of the code in C #

 static int flag; void display(List<int> input, int numOfElements, List<int> solution, int index) { Dictionary<int, int> map = new Dictionary<int, int>(); for (int i = 0; i < numOfElements; i++) { if (map.ContainsKey(input[i])) map[input[i]] = map[input[i]] + 1; else map.Add(input[i], 1); } Console.WriteLine("First Subset "); for (int i = 0; i < index; i++) { Console.Write(solution[i] + " "); map[solution[i]] = map[solution[i]] - 1; } Console.WriteLine(); Console.WriteLine("Second Subset "); foreach (var kv in map) { var value = kv.Value; while (value-- > 0) Console.Write(kv.Key + " "); } } // this function is implemented to find the set of elemtns that sum to required value and remaining array elements will already be another set void subset(List<int> input, int numOfElements, List<int> solution, int sum, int i, int index) { if (flag == 1) return; if (sum == 0) { display(input, numOfElements, solution, index); flag = 1; return; } if (sum < 0 || i > numOfElements - 1) return; subset(input, numOfElements, solution, sum, (i + 1), index); solution[index] = input[i]; subset(input, numOfElements, solution, (sum - input[i]), i + 1, index + 1); } void Main() { int totalSum = 0; List<int> input = new List<int> { 10, 20 , 30 , 5 , 40 , 50 , 40 , 15 }; totalSum = input.Sum(); if (totalSum % 2 == 1) Console.WriteLine("Not Possible"); int sum = totalSum / 2; List<int> solution = new List<int>() { 0, 0, 0, 0, 0, 0, 0, 0 }; flag = 0; subset(input, input.Count, solution, sum, 0, 0); if (flag == 0) Console.WriteLine("Not Possible"); } 

Answer 11

Found a solution here

 package sort; import java.util.ArrayList; import java.util.List; public class ArraySumSplit { public static void main (String[] args) throws Exception { int arr[] = {1 , 2 , 3 , 4 , 5 , 5, 1, 1, 3, 2, 1}; split(arr); } static void split(int[] array) throws Exception { int sum = 0; for(int n : array) sum += n; if(sum % 2 == 1) throw new Exception(); //impossible to split evenly List<Integer> firstPart = new ArrayList<Integer>(); List<Integer> secondPart = new ArrayList<Integer>(); if(!dfs(0, sum / 2, array, firstPart, secondPart)) throw new Exception(); // impossible to split evenly; //firstPart and secondPart have the grouped elements, print or return them if necessary. System.out.print(firstPart.toString()); int sum1 = 0; for (Integer val : firstPart) { sum1 += val; } System.out.println(" = " + sum1); System.out.print(secondPart.toString()); int sum2 = 0; for (Integer val : secondPart) { sum2 += val; } System.out.println(" = " + sum2); } static boolean dfs(int i, int limit, int[] array, List<Integer> firstPart, List<Integer> secondPart) { if( limit == 0) { for(int j = i; j < array.length; j++) { secondPart.add(array[j]); } return true; } if(limit < 0 || i == array.length) { return false; } firstPart.add(array[i]); if(dfs(i + 1, limit - array[i], array, firstPart, secondPart)) return true; firstPart.remove(firstPart.size() - 1); secondPart.add(array[i]); if(dfs(i + 1, limit, array, firstPart, secondPart)) return true; secondPart.remove(secondPart.size() - 1); return false; } } 

Answer 12

BAD greedy heuristic to solve this problem: try sorting the list from smallest to largest and split this list into two, specifying list1 = odd elements and list2 = even elements.

Answer 13

Firstly, if the elements are integers, check that the sum is evenly divided by two - if this does not succeed, it is impossible.

I would pose the problem as a binary tree, with level 0 deciding which element of set 0 is included, level 1, which determines which element of set 1 is included, etc. At any time, if the sum of one set is half the total, you are finished - success. At any time, if the sum of one set exceeds half the total, this subtree is a failure and you need to back up. At this point, this is a tree traversal issue.

Answer 14

Algorithm:

Step 1) Divide the array into two Step 2) If the sum is equal, the split is completed
Step 3) Change one element from array 1 with array2, guided by four rules:
IF the sum of the elements in array 1 is less than the sum of the elements in array2
Rule1:
Find the number in array 1 that is less than the number in array2 so that replacing these elements does not increase the amount of array1 for the expected amount. If found, replace the items and return.
Rule2:
If Rule1 is not invalid, find the number in array 1 that is greater than the number in array2 in such a way that the difference between any two numbers in array 1 and array2 is no less than the difference between these two numbers.
ELSE
Rule3:
Find the number in array 1 that is greater than the number in array2, so that replacing these elements does not reduce the amount of array1 for the expected amount. If found, replace the items and return.
Rule4:
If Rule3 is not invalid, find the number in array 1 that is less than the number in array2 in such a way that the difference between any two numbers in array 1 and array2 is no less than the difference between these two numbers.
Step 5) Go to step 2 until the swap leads to an array with the same set of found elements. Setp 6) If it repeats, this array cannot be divided into two halves with an equal sum. Current array set

Note. The approach used is to replace an element from one array with another in such a way that the total amount is as close as possible to the expected amount.

The java program is available in Java Code.

Answer 15

 package PACKAGE1; import java.io.*; import java.util.Arrays; public class programToSplitAnArray { public static void main(String args[]) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); System.out.println("enter the no. of elements to enter"); int n = Integer.parseInt(br.readLine()); int x[] = new int[n]; int half; for (int i = 0; i < n; i++) { x[i] = Integer.parseInt(br.readLine()); } int sum = 0; for (int i = 0; i < n; i++) { sum = sum + x[i]; } if (sum % 2 != 0) { System.out.println("the sum is odd and cannot be divided"); System.out.println("The sum is " + sum); } else { boolean div = false; half = sum / 2; int sum1 = 0; for (int i = 0; i < n; i++) { sum1 = sum1 + x[i]; if (sum1 == half) { System.out.println("array can be divided"); div = true; break; } } if (div == true) { int t = 0; int[] array1 = new int[n]; int count = 0; for (int i = 0; i < n; i++) { t = t + x[i]; if (t <= half) { array1[i] = x[i]; count++; } } array1 = Arrays.copyOf(array1, count); int array2[] = new int[n - count]; int k = 0; for (int i = count; i < n; i++) { array2[k] = x[i]; k++; } System.out.println("The first array is "); for (int m : array1) { System.out.println(m); } System.out.println("The second array is "); for (int m : array2) { System.out.println(m); } } else { System.out.println("array cannot be divided"); } } } } 

Answer 16

Please try this and let me know if you don’t work. Hope this helps you.

 static ArrayList<Integer> array = null; public static void main(String[] args) throws IOException { ArrayList<Integer> inputArray = getinputArray(); System.out.println("inputArray is " + inputArray); Collections.sort(inputArray); int totalSum = 0; Iterator<Integer> inputArrayIterator = inputArray.iterator(); while (inputArrayIterator.hasNext()) { totalSum = totalSum + inputArrayIterator.next(); } if (totalSum % 2 != 0) { System.out.println("Not Possible"); return; } int leftSum = inputArray.get(0); int rightSum = inputArray.get(inputArray.size() - 1); int currentLeftIndex = 0; int currentRightIndex = inputArray.size() - 1; while (leftSum <= (totalSum / 2)) { if ((currentLeftIndex + 1 != currentRightIndex) && leftSum != (totalSum / 2)) { currentLeftIndex++; leftSum = leftSum + inputArray.get(currentLeftIndex); } else break; } if (leftSum == (totalSum / 2)) { ArrayList<Integer> splitleft = new ArrayList<Integer>(); ArrayList<Integer> splitright = new ArrayList<Integer>(); for (int i = 0; i <= currentLeftIndex; i++) { splitleft.add(inputArray.get(i)); } for (int i = currentLeftIndex + 1; i < inputArray.size(); i++) { splitright.add(inputArray.get(i)); } System.out.println("splitleft is :" + splitleft); System.out.println("splitright is :" + splitright); } else System.out.println("Not possible"); } public static ArrayList<Integer> getinputArray() { Scanner scanner = new Scanner(System.in); array = new ArrayList<Integer>(); int size; System.out.println("Enter the Initial array size : "); size = scanner.nextInt(); System.out.println("Enter elements in the array"); for (int j = 0; j < size; j++) { int element; element = scanner.nextInt(); array.add(element); } return array; } 

}

Answer 17

  public boolean splitBetween(int[] x){ int sum=0; int sum1=0; if (x.length==1){ System.out.println("Not a valid value"); } for (int i=0;i<x.length;i++){ sum=sum+x[i]; System.out.println(sum); for (int j=i+1;j<x.length;j++){ sum1=sum1+x[j]; System.out.println("SUm1:"+sum1); } if(sum==sum1){ System.out.println("split possible"); System.out.println("Sum: " +sum +" Sum1:" + sum1); return true; }else{ System.out.println("Split not possible"); } sum1=0; } return false; } 

Answer 18

https://github.com/ShubhamAgrahari/DRjj/blob/master/Subarray_Sum.java

 package solution; 

import java.util.Scanner;

Public Class Solution {

static int SplitPoint(int arr[], int n) { int leftSum = 0; for (int = 0; < n; i++) leftSum += arr[i]; int rightSum = 0; for (int = n-1; >= 0; i--) { rightSum += arr[i]; leftSum -= arr[i]; if (rightSum == leftSum) return i; } return -1; } static void output(int arr[], int n) { int s = SplitPoint(arr, n); if (s == -1 || s == n ) { System.out.println("Not Possible" ); return; } for (int = 0; < n; i++) { if(s == i) System.out.println(); System.out.print(arr[i] + " "); } } public static void main (String[] args) { Scanner sc= new Scanner(System.in); System.out.println("Enter Array Size"); int n = sc.nextInt(); int arr[]= new int[n]; for(int i=0;i<n;i++) { arr[i]=sc.nextInt(); } output(arr, n); } }

Answer 19

very simple solution with recursion

 public boolean splitArray(int[] nums){ return arrCheck(0, nums, 0); } public boolean arrCheck(int start, int[] nums, int tot){ if(start >= nums.length) return tot == 0; if(arrCheck(start+1, nums, tot+nums[start])) return true; if(arrCheck(start+1, nums, tot-nums[start])) return true; return false; }