如何将一个数组最优地划分为两个子数组，使两个子数组中的元素之和相同，否则会报错？
示例 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
该数组不能分成两个等和的数组。
问问题
83791 次
23 回答
21
存在一个涉及动态编程的解决方案，它在 中运行O(n*TotalSum)，其中n是数组中元素的数量，TotalSum是它们的总和。
第一部分包括计算可以通过向数组添加元素来创建的所有数字的集合。
对于一个大小的数组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中。
于 2011-05-05T13:32:37.990 回答
11
这称为分区问题。对于一些特殊情况，有最优解。但是，一般来说，这是一个 NP 完全问题。
于 2011-05-05T13:33:19.917 回答
6
在其常见的变体中，这个问题施加了 2 个约束，并且可以以更简单的方式完成。
- 如果分区只能沿着数组长度的某处进行（我们不考虑元素乱序）
- 没有负数。
然后起作用的算法可能是：
- 有 2 个变量，leftSum 和 rightSum
- 从数组的左侧开始递增 leftSum，从右侧开始递增 rightSum。
- 尝试纠正其中的任何不平衡。
以下代码执行上述操作：
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
当然，如果元素可以乱序组合，它确实会变成具有复杂性的分区问题。
于 2013-09-21T11:25:41.110 回答
1
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='')
于 2020-06-01T22:14:41.493 回答
0
这个问题说，如果一个数组可以有两个子数组，它们的元素之和相同。所以应该返回一个布尔值。我找到了一种有效的算法：算法：过程步骤1：将一个空数组作为容器，对初始数组进行排序并保留在空数组中。第二步：现在取两个动态可分配数组，从辅助数组中取出最高和第二高分别保存在两个子数组中，并从辅助数组中删除。第 3 步：比较子数组中元素的总和，总和较小的有机会获取数组中剩余的最高元素，然后从容器中删除。第 4 步：循环到第 3 步，直到容器为空。步骤5：比较两个子数组的总和，如果它们相同，则返回true，否则返回false。
// 这个问题的复杂性在于可能有很多组合，但是这个算法有一个独特的方式。
于 2011-05-06T02:09:20.573 回答
0
@Gal Subset-Sum 问题是 NP-Complete 并且具有 O(n*TotalSum) 伪多项式动态规划算法。但是这个问题不是NP-Complete。这是一种特殊情况，实际上可以在线性时间内解决。
在这里，我们正在寻找一个索引，我们可以将数组拆分为具有相同总和的两部分。检查以下代码。
分析：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);
}
}
于 2013-05-16T16:48:01.290 回答
0
尝试了不同的解决方案。除了 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 的正数）如果有人遇到问题，请告诉我。
于 2014-04-13T22:08:01.980 回答
0
这是该问题的递归解决方案，一种非递归解决方案可以使用辅助方法在 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);
}
于 2015-04-12T02:17:34.763 回答
0
在这里找到解决方案
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;
}
}
于 2018-08-26T20:17:37.267 回答
0
如果总和为偶数，此 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])
于 2019-05-30T06:06:59.783 回答
0
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))
于 2019-11-11T13:30:34.287 回答
0
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,))
>>>
于 2020-02-27T12:58:36.323 回答
0
它的 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
于 2022-02-11T23:40:21.173 回答
-1
首先，如果元素是整数，请检查总数是否可以被 2 整除——如果不成功是不可能的。
我会将问题设置为二叉树，级别 0 决定哪个集合元素 0 进入，级别 1 决定哪个集合元素 1 进入，等等。在任何时候，如果一个集合的总和是总数的一半，你重新完成 - 成功。在任何时候，如果一组的总和超过总数的一半，则该子树是失败的，您必须备份。在这一点上，这是一个树遍历问题。
于 2011-05-05T13:22:01.647 回答
-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;
}
}
// 贪婪的方法 //
于 2011-05-06T06:25:33.363 回答
-1
算法：
步骤 1) 将数组一分为二
步骤 2) 如果总和相等，则拆分完成
步骤 3) 将数组 1 中的一个元素与数组 2 交换，遵循以下四个规则：
如果数组 1 中的元素之和小于元素之和在array2
规则1：
在array1 中找到一个小于array2 中的数字，这样交换这些元素时，不会使array1 的总和超过预期的总和。如果找到，交换元素并返回。
规则2：
如果不满足Rule1，则在array1 中找到一个大于array2 的数，使array1 和array2 中任意两个数的差不小于这两个数的差。
ELSE
规则 3：
在 array1 中找到一个大于 array2 中的数字的数字，以交换这些元素的方式，不要将 array1 的总和减少到超出预期的总和。如果找到，交换
元素并返回。
规则4：
如果不满足Rule3，则在array1 中找到一个小于array2 的数，使array1 和array2 中任意两个数的差不小于这两个数的差。
步骤 5) 转到步骤 2，直到交换结果产生一个数组，其中已经遇到了相同的元素集 Setp 6) 如果发生重复，则该数组不能分成总和相等的两半。当前的数组集合或在此重复之前形成的集合应该是数组的最佳拆分。
注意：所采用的方法是将元素从一个数组交换到另一个数组，以使结果总和尽可能接近预期总和。
Java 程序可在Java 代码中获得
于 2013-09-13T07:40:39.803 回答
-1
我在一次采访中被问到这个问题，我给出了以下简单的解决方案，因为我之前在任何网站上都没有看到这个问题。
假设数组 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。如果为真，我们得到的索引为 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);
于 2013-02-23T16:02:36.893 回答
-1
解决这个问题的一个糟糕的贪婪启发式方法：尝试从最小到最大对列表进行排序，然后通过让 list1 = 奇数元素和 list2 = 偶数元素将该列表分成两个。
于 2011-05-05T13:09:27.207 回答
-1
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");
}
}
}
}
于 2014-01-27T08:31:55.137 回答
-1
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;
}
于 2016-04-04T05:35:08.723 回答
-1
请试试这个，如果不起作用，请告诉我。希望它会帮助你。
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;
}
}
于 2016-03-31T11:50:53.403 回答
-2
https://github.com/ShubhamAgrahari/DRjj/blob/master/Subarray_Sum.java
一揽子解决方案；导入 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); } }
于 2018-12-21T09:44:47.787 回答
-2
非常简单的递归解决方案
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;
}
于 2017-08-23T21:23:22.203 回答