如何最佳地将数组划分为两个子数组，以使两个子数组中的元素之和相同，否则会出错？

Question

如何最佳地将数组划分为两个子数组，以使两个子数组中的元素之和相同，否则给出错误？

示例 1

给定数组

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

它可以被划分为

10, 20, 30, 5, 40

并且

50, 40, 15

每个子数组的总和为 105。

示例 2

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

该数组不能分为 2 个总和相等的数组。

Answer 1

存在一个涉及动态规划的解决方案，其运行时间为 O(n*TotalSum)，其中 n 是数组中的元素数量，TotalSum< /code> 是它们的总和。

第一部分包括计算可以通过向数组添加元素来创建的所有数字的集合。

对于大小为 n 的数组，我们将其称为 T(n)，

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

（正确性的证明是通过归纳法来证明的，就像大多数递归函数一样。）

此外，记住动态矩阵中的每个单元格，为了创建它而添加的元素。

简单的复杂性分析将表明这是在 O(n*TotalSum) 内完成的。

计算 T(n) 后，在集合中搜索恰好等于 TotalSum / 2 大小的元素。

如果存在这样的项目，则创建它的元素加在一起等于 TotalSum / 2，并且不属于其创建的元素也等于 TotalSum / 2 （TotalSum - TotalSum / 2 = TotalSum / 2）。

这是一个伪多项式解。 AFAIK，这个问题不知道在 P 中。

Answer 2

这称为分区问题。对于一些特殊情况有最优的解决方案。然而，一般来说，这是一个NP完全问题。

Answer 3

在其常见变体中，这个问题施加了 2 个约束，并且可以通过更简单的方式来完成。

1. 如果只能沿着数组长度的某个位置进行分区（我们不考虑乱序的元素），
2. 则不存在负数。

然后起作用的算法可能是：

1. 有 2 个变量，leftSum 和 rightSum
2. 开始从数组的左侧递增 leftSum，从数组的右侧递增 rightSum。
3. 尝试纠正其中的任何不平衡。

以下代码执行上述操作：

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

输出：

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

当然，如果元素可以无序组合，那么它确实会变成具有所有复杂性的分区问题。

Answer 4

a=[int(g) for g in input().split()]     #for taking the array as input in a 
                                     single line
leftsum=0
n=len(a)
for i in range(n):                      
    leftsum+=a[i]                       #calculates the sum of first subarray             
    rightsum=0
    for j in range(i+1):
        rightsum+=a[j]                  #calculates the sum of other subarray
    if leftsum==rightsum:
        pos=i+1                         #if the sum of subarrays are equal, 
        break                           set position where the condition
                                        gets satisfied and exit the loop 
    else:
        pos=-1                          #if the sum of subarrays is not 
                                        equal, set position to -1 
if pos=-1 or pos=n:
    print('It is not possible.')
else:                                   #printing the sub arrays`
    for k in range(n):
        if pos=k:
            print('')
        print(str(a[k]),end='')

Answer 5

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

// 这个问题的复杂性在于可能有多种组合，但这个算法有一种独特的方式。

Answer 6

尝试了不同的解决方案。除了 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];
        }
    }

}

我已经测试过。 （它适用于大于 0 的正数）如果有人遇到问题，请告诉我。

Answer 7

这是问题的递归解决方案，一种非递归解决方案可以使用辅助方法在 for 循环中获取索引 0 到当前索引的总和，另一种解决方案可以获取同一当前索引到最后，有效。现在，如果您想将元素放入数组并比较总和，首先找到标记溢出的点（索引），其中两侧的总和相等，然后获取一个列表并在该索引和另一个列表之前添加值在该索引之后。

这是我的（递归），它仅确定是否有地方可以分割数组，以便一侧的数字之和等于另一侧的数字之和。担心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);
}

Answer 8

找到解决方案此处

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 9

    def listSegmentation(theList):
    newList = [[],[]]
    print(theList)

    wt1 = 0
    wt2 = 0
    dWt = 0

    for idx in range(len(theList)):
        wt = theList[idx]

        if (wt > (wt1 + wt2) and wt1 > 0 and wt2 > 0):
            newList[0] = newList[0] + newList[1]
            newList[1] = []
            newList[1].append(wt)
            wt1 += wt2
            wt2 = wt 
        elif ((wt2 + wt) >= (wt1 + wt)):
            wt1 += wt
            newList[0].append(wt)
        elif ((wt2 + wt) < (wt1 + wt)):
            wt2 += wt
            newList[1].append(wt)

    #Balancing
    if(wt1 > wt2):
        wtDiff = sum(newList[0]) - sum(newList[1])
        ls1 = list(filter(lambda x: x <= wtDiff, newList[0]))
        ls2 = list(filter(lambda x: x <= (wtDiff/2) , newList[1]))

        while len(ls1) > 0 or len(ls2) > 0:
            if len(ls1) > 0:
                elDif1 = max(ls1)
                newList[0].remove(elDif1)
                newList[1].append(elDif1)

            if len(ls2) > 0:
                elDif2 = max(ls2)
                newList[0].append(elDif2)
                newList[1].remove(elDif2)

            wtDiff = sum(newList[0]) - sum(newList[1])
            ls1 = list(filter(lambda x: x <= wtDiff, newList[0]))
            ls2 = list(filter(lambda x: x <= (wtDiff/2) , newList[1]))


    if(wt2 > wt1):
        wtDiff = sum(newList[1]) - sum(newList[0])
        ls2 = list(filter(lambda x: x <= wtDiff, newList[1]))
        ls1 = list(filter(lambda x: x <= (wtDiff/2) , newList[0]))
        while len(ls1) > 0 or len(ls2) > 0:
            if len(ls1) > 0:
                elDif1 = max(ls1)
                newList[0].remove(elDif1)
                newList[1].append(elDif1)

            if len(ls2) > 0:
                elDif2 = max(ls2)
                newList[0].append(elDif2)
                newList[1].remove(elDif2)

            wtDiff = sum(newList[1]) - sum(newList[0])
            ls2 = list(filter(lambda x: x <= wtDiff, newList[1]))
            ls1 = list(filter(lambda x: x <= (wtDiff/2) , newList[0]))
            print(ls1, ls2)


    print(sum(newList[0]),sum(newList[1]))
    return newList


#Test cases
lst1 = [4,9,8,3,11,6,13,7,2,25,28,60,19,196]
lst2 = [7,16,5,11,4,9,15,2,1,13]
lst3 = [8,17,14,9,3,5,19,11,4,6,2]

print(listSegmentation(lst1))
print(listSegmentation(lst2))
print(listSegmentation(lst3))

Answer 10

如果总和为偶数，此 Python3 函数会将数字列表拆分并平衡为两个总和相等的单独列表。

Python3 solution:

def can_partition(a):
    mylist1 = []
    mylist2 = []
    sum1 = 0
    sum2 = 0

    for items in a:
        # Take total and divide by 2.
        total = sum(a)
        if total % 2 == 0:
            half = total//2
        else:
            return("Exiting, sum has fractions, total %s half %s" % (total, total/2))       
        mylist1.append(items)
    print('Total is %s and half is %s' %(total, total/2))

    for i in a:
        sum1 = sum(mylist1)
        sum2 = sum(mylist2)
        if sum2 < half:
            mypop = mylist1.pop(0)
            mylist2.append(mypop)

    # Function to swtich numbers between the lists if sums are uneven.           
    def switchNumbers(list1, list2,switch_diff):
        for val in list1:
            if val == switch_diff:
                val_index = list1.index(val)
                new_pop = list1.pop(val_index)
                list2.append(new_pop)

    #Count so while do not get out of hand 
    count = len(a)       
    while count != 0: 
        sum1 = sum(mylist1)
        sum2 = sum(mylist2)
        if sum1 > sum2:
            diff = sum1 -half
            switchNumbers(mylist1, mylist2, diff)
            count -= 1
        elif sum2 > sum1:
            diff = sum2 - half
            switchNumbers(mylist2, mylist1, diff)
            count -= 1
        else:
            if sum1 == sum2:
                print('Values of half, sum1, sum2 are:',half, sum1,sum2)
                break
        count -= 1

    return (mylist1, mylist2)

b = [ 2, 3, 4, 2, 3, 1, 2, 5, 4, 4, 2, 2, 3, 3, 2 ]
can_partition(b)

Output:
Total is 42 total, half is 21.0
Values of half, sum1 & sum2 are : 21 21 21

([4, 4, 2, 2, 3, 3, 2, 1], [2, 3, 4, 2, 3, 2, 5])

Answer 11

python中的非最优解决方案，

from itertools import permutations

def get_splitted_array(a):
  for perm in permutations(a):
    l1 = len(perm)
    for i in range(1, l1):
      if sum(perm[0:i]) == sum(perm[i:l1]):
        return perm[0:i], perm[i:l1]

>>> a = [6,1,3,8]
>>> get_splitted_array(a)
((6, 3), (1, 8))
>>> a = [5,9,20,1,5]
>>> 
>>> get_splitted_array(a)
((5, 9, 1, 5), (20,))
>>> 

Answer 12

其 O(n) 时间和 O(n) 空间

def equal_subarr(arr):
    n=len(arr)
    post_sum = [0] * (n- 1) + [arr[-1]]
    for i in range(n - 2, -1, -1):
        post_sum[i] = arr[i] + post_sum[i + 1]

    prefix_sum = [arr[0]] + [0] * (n - 1)
    for i in range(1, n):
        prefix_sum[i] = prefix_sum[i - 1] + arr[i]

    for i in range(n - 1):
        if prefix_sum[i] == post_sum[i + 1]:
            return [arr[:i+1],arr[i+1:]]
    return -1


arr=[10,  20 , 30 , 5 , 40 , 50 , 40 , 15]
print(equal_subarr(arr))
>>> [[10, 20, 30, 5, 40], [50, 40, 15]]

arr=[10,  20,  30,  5,  40,  50,  40,  10]
print(equal_subarr(arr))
>>> -1

Answer 13

首先，如果元素是整数，请检查总数是否能被二整除——如果不是，则不可能成功。

我会将问题设置为二叉树，级别 0 决定元素 0 进入哪个集合，级别 1 决定元素 1 进入哪个集合，依此类推。在任何时候，如果一组的总和是总数的一半，那么你'重新完成-成功。任何时候，如果一组的总和超过总数的一半，则该子树失败，您必须备份。这时候就是一个树遍历问题了。

Answer 14

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

}

// 贪婪方法 //

Answer 15

我在采访中被问到这个问题，我给出了以下简单的解决方案，因为我之前没有在任何网站上看到过这个问题。

假设数组 A = {45,10,10,10,10,5}
然后，分割将在索引 = 1（基于 0 的索引）处进行，这样我们就有两个相等的总和集 {45} 和 {10,10,10,10,5}

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

/*
将两个索引指针移向数组的中间，直到 currentRightIndex != currentLeftIndex。如果左侧元素之和仍然小于或等于'rightIndex'右侧元素之和，则增加leftIndex。最后，检查是否leftSum == rightSum。如果为 true，我们得到的索引为 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);

Answer 16

@Gal Subset-Sum 问题是 NP 完全问题，并且具有 O(n*TotalSum) 伪多项式动态规划算法。但这个问题不是NP完全问题。这是一个特殊情况，实际上可以在线性时间内解决。

在这里，我们正在寻找一个索引，可以将数组分成具有相同总和的两部分。
检查以下代码。

分析：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);
     }

}

Answer 17

算法：

步骤 1) 将数组分成两部分
步骤2）如果总和相等，则分割完成
步骤 3) 将 array1 中的一个元素与 array2 交换，遵循以下四个规则：
   如果 array1 中的元素之和小于 array2 中的元素之和
    规则1：
      在 array1 中找到一个小于 array2 中的数字，方法是交换
      这些元素不会将 array1 的总和增加到超出预期总和。如果找到，则交换
      元素并返回。
    规则2：
      如果不满足Rule1，则在array1中查找比array2中的数字大的数字
      这样 array1 和 array2 中任意两个数的差不小于
      这两个数字之间的差异。
   其他
    规则3：
      在 array1 中找到一个比 array2 中的数字大的数字，通过交换这些数字
      元素，不要将 array1 的总和减少到超出预期总和。如果找到，则交换
       元素并返回。
    规则4：
      如果不满足Rule3，则在array1中查找小于array2中的数字
      这样 array1 和 array2 中任意两个数的差不小于
      这两个数字之间的差异。
步骤 5) 转到步骤 2，直到交换结果得到一个已遇到相同元素集的数组
Setp 6) 如果发生重复，则该数组不能分成总和相等的两半。当前的数组集合或在此重复之前形成的数组应该是数组的最佳分割。

注意：所采取的方法是将元素从一个数组交换到另一个数组，以使所得总和尽可能接近预期总和。

java 程序位于 Java 代码

Answer 18

请尝试这个，如果不起作用请告诉我。希望它会对您有所帮助。

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 19

    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 20

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 21

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

Answer 22

非常简单的递归解决方案

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

Answer 23

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

package solution;


导入java.util.Scanner；

公共课解决方案{

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

} }