如何最优地将数组划分为两个子数组，使两个数组中的元素之和相同，否则会产生错误?

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.

每个子数组加起来是105。

Example 2

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

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

数组不能被分成两个等和的数组。

16 个解决方案

#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.

存在一种解决方案，它涉及动态编程，运行在O(n*TotalSum)中，其中n是数组中的元素数量，TotalSum是它们的总和。

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

对于一个大小为n的数组，我们称它为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).

简单的复杂性分析将显示这是在O(n*TotalSum)中完成的。

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

在计算T(n)之后，搜索集合中与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).

如果存在这样的项，那么创建它的元素相加，等于TotalSum / 2，而不属于其创建的元素也等于TotalSum / 2 (TotalSum - TotalSum / 2 = TotalSum / 2)。

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

这是一个伪多项式解。AFAIK，这个问题并不存在于P中。

#2

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

这叫做划分问题。对于某些特殊情况有最优解。然而，总的来说，这是一个np完备问题。

#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. 如果分区只能沿着数组的长度完成(我们不认为元素无序)
3. There are no negative numbers.
4. 没有负数。

The algorithm that then works could be:

这样的算法可以是:

1. Have 2 variables, leftSum and rightSum
2. 有两个变量，左和右和
3. Start incrementing leftSum from the left, and rightSum from the right of the array.
4. 开始从左边递增leftSum，从数组右边递增rightSum。
5. Try to correct any imbalance in it.
6. 试着纠正其中的不平衡。

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.

这个问题说如果一个数组可以有两个子数组它们的元素和是一样的。因此，应该返回一个布尔值。我找到了一种高效的算法:Algo:步骤1:将空数组作为容器，对初始数组进行排序，并保存在空数组中。步骤2:现在取两个动态的可分配数组，从辅助数组中取出最高的和第二高的，分别保存在两个子数组中，并从辅助数组中删除。步骤3:比较子数组中元素的和，较小的和将有机会在数组中获取最大的剩余元素，然后从容器中删除。步骤4:循环到步骤3，直到容器为空。步骤5:比较两个子数组的和，如果它们是相同的返回真否则为假。

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

//这个问题的复杂性在于，可能会有很多组合，但是这个algo有一个独特的方法。

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

假设数组A ={45,10,10,10, 5}那么，分割将在index = 1(基于0的索引)处，这样我们就有了两个相等的和集{45}和{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). */

将两个索引指针移动到数组的中间，直到currentRightIndex != currentLeftIndex。如果左元素的和仍然小于或等于右元素的和，则增加左索引。最后，检查leftSum = rightSum。如果为真，我们得到的索引为currentLeftIndex+1(或者简单地称为currentRightIndex，因为在这种情况下currentRightIndex将等于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);

#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.

@Gal子集-和问题是np完备问题，具有O(n*TotalSum)伪多项式动态规划算法。但是这个问题并不是np完全的。这是一个特殊的情况，事实上这个可以用线性时间来解。

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.

分析:O(n)，因为算法只遍历数组，不使用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).

尝试了一种不同的解决方案。除了Wiki解决方案(分区问题)。

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.

我已经测试了。(当正数大于0时，效果很好)如果有任何问题，请告诉我。

#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.

这是一个递归解决这个问题,一个非递归的解决方案可以使用一个辅助方法来获取索引0到电流的总和指数一个for循环,另一个可以得到相同的元素的总和电流指数,这工作。现在，如果您想要将元素放入数组中并比较它们的总和，首先要找到点(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.

这是我的(递归)，它只确定是否有地方分割数组，以便一边的数字之和等于另一边的数字之和。担心indexOutOfBounds(在递归中很容易发生)，一个微小的错误可能会被证明是致命的，并产生大量异常和错误。

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

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

首先，如果元素是整数，检查总能被2整除——如果不能成功的话。

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.

我将问题设置为一个二叉树，0级决定哪个集合元素0进入，1级决定哪个集合元素1进入，等等。任何时候，如果一个集合的总和是总数的一半，你就完成了——成功。在任何时候，如果一个集合的总和超过总数的一半，那么这个子树就是失败的，你必须备份。在这一点上，它是一个树遍历问题。

#10

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 //

//贪婪的方法

#11

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.

步骤1)数组分割成两个步骤2)如果之和等于,分裂完成步骤3)交换一个元素从array1 array2,遵循四个规则:如果array1中元素之和小于元素之和array2规则1:找到一个在array1数量小于在array2交换这些元素以这样一种方式,并不会增加array1超出预期金额的总和。如果找到，交换元素并返回。Rule2:如果Rule1不满足，可以在array1中找到一个大于array2中的一个数，这样array1和array2中任意两个数的差都不会小于这两个数的差。ELSE Rule3:在array1中找到一个大于array2中数字的数，这样就可以交换这些元素，不会使array1的和小于期望的总和。如果找到，交换元素并返回。Rule4:如果Rule3不满足，在array1中找到一个小于array2中的数字的数字，在array1和array2中任意两个数字之间的差值都不小于这两个数字之间的差值。步骤5)转到步骤2，直到交换结果在一个数组中产生与已经遇到的Setp 6相同的元素集)如果重复发生，这个数组不能被分割成两半，并具有相等的和。数组的当前集合或在此重复之前形成的集合应该是数组的最佳分割。

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

java程序可以在java代码中使用

#12

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

}

}

#13

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

#14

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

}

#15

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.

解决这个问题的一种糟糕的贪婪启发式方法是:尝试从最小到最大排序列表，并通过让list1 =奇数元素和list2 =偶数元素将该列表分成两个。

#16

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