How to optimally divide an array into two subarray

问题:

How to optimally divide an array into two subarrays so that sum of elements in both subarrays is same, otherwise give an error?

Example 1

Given the array

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

It can be divided as

10, 20, 30, 5, 40

and

50, 40, 15

Each subarray sums up to 105.

Example 2

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

The array cannot be divided into 2 arrays of an equal sum.

回答1:

There exists a solution, which involves dynamic programming, that runs in O(n*TotalSum), where n is the number of elements in the array and TotalSum is their total sum.

The first part consists in calculating the set of all numbers that can be created by adding elements to the array.

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

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

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

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

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

After calculating T(n), search the set for an element exactly the size of TotalSum / 2.

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

This is a pseudo-polynomial solution. AFAIK, this problem is not known to be in P.

回答2:

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

回答3:

In its common variant, this problem imposes 2 constraints and it can be done in an easier way.

1. If the partition can only be done somewhere along the length of the array (we do not consider elements out of order)
2. There are no negative numbers.

The algorithm that then works could be:

1. Have 2 variables, leftSum and rightSum
2. Start incrementing leftSum from the left, and rightSum from the right of the array.
3. Try to correct any imbalance in it.

The following code does the above:

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

The output:

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

Ofcourse, if the elements can be combined out-of-order, it does turn into the partition problem with all its complexity.

回答4:

This Problem says that if an array can have two subarrays with their sum of elements as same. So a boolean value should be returned. I have found an efficient algorithm : Algo: Procedure Step 1: Take an empty array as a container , sort the initial array and keep in the empty one. Step 2: now take two dynamically allocatable arrays and take out highest and 2nd highest from the auxilliary array and keep it in the two subarrays respectively , and delete from the auxiliary array. Step 3: Compare the sum of elements in the subarrays , the smaller sum one will have chance to fetch highest remaining element in the array and then delete from the container. Step 4: Loop thru Step 3 until the container is empty. Step 5: Compare the sum of two subarrays , if they are same return true else false.

// The complexity with this problem is that there may be many combinations possible but this algo has one unique way .

回答5:

I was asked this question in an interview, and I gave below simple solution, as I had NOT seen this problem in any websiteS earlier.

Lets say Array A = {45,10,10,10,10,5} Then, the split will be at index = 1 (0-based index) so that we have two equal sum set {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 two index pointers towards mid of the array untill currentRightIndex != currentLeftIndex. Increase leftIndex if sum of left elements is still less than or equal to sum of elements in right of 'rightIndex'.At the end,check if leftSum == rightSum. If true, we got the index as currentLeftIndex+1(or simply currentRightIndex, as currentRightIndex will be equal to currentLeftIndex+1 in this case). */

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

回答6:

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

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

Analysis: O(n), as the algorithm only iterates 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);
     }

}

回答7:

Tried a different solution . other than Wiki solutions (Partition Problem).

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 positive number greater than 0) please let me know if any one face issue.

回答8:

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

回答9:

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

回答10:

First, if the elements are integers, check that the total is evenly divisible by two- if it isn't success isn't possible.

I would set up the problem as a binary tree, with level 0 deciding which set element 0 goes into, level 1 deciding which set element 1 goes into, etc. At any time if the sum of one set is half the total, you're done- success. At any time if the sum of one set is more than half the total, that sub-tree is a failure and you have to back up. At that point it is a tree traversal problem.

回答11:

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

}

// The Greedy approach //

回答12:

Algorithm:

Step 1) Split the array into two
Step 2) If the sum is equal, split is complete
Step 3) Swap one element from array1 with array2, guided by the four rules:
   IF the sum of elements in array1 is less than sum of elements in array2
      Rule1:
         Find a number in array1 that is smaller than a number in array2 in such a way that swapping of          these elements, do not increase the sum of array1 beyond the expected sum. If found, swap the          elements and return.
      Rule2:
         If Rule1 is not is not satisfied, Find a number in array1 that is bigger than a number in array2 in          such a way that the difference between any two numbers in array1 and array2 is not smaller than          the difference between these two numbers.
   ELSE
      Rule3:
         Find a number in array1 that is bigger than a number in array2 in such a way that swapping these          elements, do not decrease the sum of array1 beyond the expected sum. If found, swap the
         elements and return.
      Rule4:
         If Rule3 is not is not satisfied, Find a number in array1 that is smaller than a number in array2 in          such a way that the difference between any two numbers in array1 and array2 is not smaller than          the difference between these two numbers.
Step 5) Go to Step2 until the swap results in an array with the same set of elements encountered already Setp 6) If a repetition occurs, this array cannot be split into two halves with equal sum. The current set of           arrays OR the set that was formed just before this repetition should be the best split of the array.

Note: The approach taken is to swap element from one array to another in such a way that the resultant sum is as close to the expected sum.

The java program is available at Java Code

回答13:

Please try this and let me know if not working. Hope it will 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;
}

}

回答14:

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

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

}

回答16:

A BAD greedy heuristic to solve this problem: try sorting the list from least to greatest, and split that list into two by having list1 = the odd elements, and list2 = the even elements.

回答17:

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 i = 0 ; i < n ; i++) 
    leftSum += arr[i]; 

int rightSum = 0; 

for (int i = n-1; i >= 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 i = 0; i < 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); 

} } 

回答18:

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