# 算法题：将一个数组拆分成两个相等的和子数组

2021年4月14日14:56:25 发表评论 752 次浏览

## 本文概述

``````Input : Arr[] = { 1 , 2 , 3 , 4 , 5 , 5  }
Output :  { 1 2 3 4 }
{ 5 , 5 }

Input : Arr[] = { 4, 1, 2, 3 }
Output : {4 1}
{2 3}

Input : Arr[] = { 4, 3, 2, 1}
Output : Not Possible``````

## C++

``````//C++ program to split an array into Two
//equal sum subarrays
#include<bits/stdc++.h>
using namespace std;

//Returns split point. If not possible, then
//return -1.
int findSplitPoint( int arr[], int n)
{
int leftSum = 0 ;

//traverse array element
for ( int i = 0; i <n; i++)
{
//add current element to left Sum
leftSum += arr[i] ;

//find sum of rest array elements (rightSum)
int rightSum = 0 ;
for ( int j = i+1 ; j <n ; j++ )
rightSum += arr[j] ;

//split point index
if (leftSum == rightSum)
return i+1 ;
}

//if it is not possible to split array into
//two parts
return -1;
}

//Prints two parts after finding split point using
//findSplitPoint()
void printTwoParts( int arr[], int n)
{
int splitPoint = findSplitPoint(arr, n);

if (splitPoint == -1 || splitPoint == n )
{
cout <<"Not Possible" <<endl;
return ;
}
for ( int i = 0; i <n; i++)
{
if (splitPoint == i)
cout <<endl;
cout <<arr[i] <<" " ;
}
}

//driver program
int main()
{
int arr[] = {1 , 2 , 3 , 4 , 5 , 5 };
int n = sizeof (arr)/sizeof (arr[0]);
printTwoParts(arr, n);
return 0;
}``````

## Java

``````//Java program to split an array
//into two equal sum subarrays
import java.io.*;

class GFG {

//Returns split point. If
//not possible, then return -1.
static int findSplitPoint( int arr[], int n)
{

int leftSum = 0 ;

//traverse array element
for ( int i = 0 ; i <n; i++)
{
//add current element to left Sum
leftSum += arr[i] ;

//find sum of rest array
//elements (rightSum)
int rightSum = 0 ;

for ( int j = i+ 1 ; j <n ; j++ )
rightSum += arr[j] ;

//split point index
if (leftSum == rightSum)
return i+ 1 ;
}

//if it is not possible to
//split array into two parts
return - 1 ;
}

//Prints two parts after finding
//split point using findSplitPoint()
static void printTwoParts( int arr[], int n)
{

int splitPoint = findSplitPoint(arr, n);

if (splitPoint == - 1 || splitPoint == n )
{
System.out.println( "Not Possible" );
return ;
}

for ( int i = 0 ; i <n; i++)
{
if (splitPoint == i)
System.out.println();

System.out.print(arr[i] + " " );

}
}

//Driver program

public static void main (String[] args) {

int arr[] = { 1 , 2 , 3 , 4 , 5 , 5 };
int n = arr.length;
printTwoParts(arr, n);

}
}

//This code is contributed by vt_m``````

## Python3

``````# Python3 program to split an array into Two
# equal sum subarrays

# Returns split point. If not possible, then
# return -1.
def findSplitPoint(arr, n) :

leftSum = 0

# traverse array element
for i in range ( 0 , n) :

# add current element to left Sum
leftSum + = arr[i]

# find sum of rest array elements (rightSum)
rightSum = 0
for j in range (i + 1 , n) :
rightSum + = arr[j]

# split poindex
if (leftSum = = rightSum) :
return i + 1

# if it is not possible to split array into
# two parts
return - 1

# Prints two parts after finding split pousing
# findSplitPoint()
def printTwoParts(arr, n) :

splitPo = findSplitPoint(arr, n)

if (splitPo = = - 1 or splitPo = = n ) :
print ( "Not Possible" )
return

for i in range ( 0 , n) :
if (splitPo = = i) :
print ("")
print ( str (arr[i]) + ' ' , end = '')

# driver program
arr = [ 1 , 2 , 3 , 4 , 5 , 5 ]
n = len (arr)
printTwoParts(arr, n)

# This code is contributed by Manish Shaw
# (manishshaw1)``````

## C#

``````//C# program to split an array
//into two equal sum subarrays
using System;

class GFG {

//Returns split point. If
//not possible, then return -1.
static int findSplitPoint( int []arr, int n)
{

int leftSum = 0 ;

//traverse array element
for ( int i = 0; i <n; i++)
{

//add current element to left Sum
leftSum += arr[i] ;

//find sum of rest array
//elements (rightSum)
int rightSum = 0 ;

for ( int j = i+1 ; j <n ; j++ )
rightSum += arr[j] ;

//split point index
if (leftSum == rightSum)
return i+1 ;
}

//if it is not possible to
//split array into two parts
return -1;
}

//Prints two parts after finding
//split point using findSplitPoint()
static void printTwoParts( int []arr, int n)
{

int splitPoint = findSplitPoint(arr, n);

if (splitPoint == -1 || splitPoint == n )
{
Console.Write( "Not Possible" );
return ;
}

for ( int i = 0; i <n; i++)
{
if (splitPoint == i)
Console.WriteLine();

Console.Write(arr[i] + " " );
}
}

//Driver program
public static void Main ()
{
int []arr = {1 , 2 , 3 , 4 , 5 , 5 };
int n = arr.Length;
printTwoParts(arr, n);
}
}

//This code is contributed by nitin mittal``````

## PHP

``````<?php
//PHP program to split
//an array into Two
//equal sum subarrays

//Returns split point.
//If not possible, then
//return -1.
function findSplitPoint( \$arr , \$n )
{
\$leftSum = 0 ;

//traverse array element
for ( \$i = 0; \$i <\$n ; \$i ++)
{

//to left Sum
\$leftSum += \$arr [ \$i ] ;

//find sum of rest array
//elements (rightSum)
\$rightSum = 0 ;
for ( \$j = \$i + 1 ; \$j <\$n ; \$j ++ )
\$rightSum += \$arr [ \$j ] ;

//split point index
if ( \$leftSum == \$rightSum )
return \$i +1 ;
}

//if it is not possible
//to split array into
//two parts
return -1;
}

//Prints two parts after
//finding split point using
//findSplitPoint()
function printTwoParts( \$arr , \$n )
{
\$splitPoint = findSplitPoint( \$arr , \$n );

if ( \$splitPoint == -1 or \$splitPoint == \$n )
{
echo "Not Possible" ;
return ;
}
for ( \$i = 0; \$i <\$n ; \$i ++)
{
if ( \$splitPoint == \$i )
echo "\n" ;
echo \$arr [ \$i ] , " " ;
}
}

//Driver Code
\$arr = array (1 , 2 , 3 , 4 , 5 , 5);
\$n = count ( \$arr );
printTwoParts( \$arr , \$n );

//This code is contributed by anuj_67.
?>``````

``````1 2 3 4
5 5``````

2

)

An高效的解决方案首先要从左到右计算整个数组的和。现在我们从右边遍历数组, 并跟踪右边的和, 可以通过从整个和中减去当前元素来计算左边的和。

## C++

``````//C++ program to split an array into Two
//equal sum subarrays
#include<bits/stdc++.h>
using namespace std;

//Returns split point. If not possible, then
//return -1.
int findSplitPoint( int arr[], int n)
{
//traverse array element and compute sum
//of whole array
int leftSum = 0;
for ( int i = 0 ; i <n ; i++)
leftSum += arr[i];

//again traverse array and compute right sum
//and also check left_sum equal to right
//sum or not
int rightSum = 0;
for ( int i=n-1; i>= 0; i--)
{
rightSum += arr[i];

//exclude current element to the left_sum
leftSum -=  arr[i] ;

if (rightSum == leftSum)
return i ;
}

//if it is not possible to split array
//into two parts.
return -1;
}

//Prints two parts after finding split point using
//findSplitPoint()
void printTwoParts( int arr[], int n)
{
int splitPoint = findSplitPoint(arr, n);

if (splitPoint == -1 || splitPoint == n )
{
cout <<"Not Possible" <<endl;
return ;
}
for ( int i = 0; i <n; i++)
{
if (splitPoint == i)
cout <<endl;
cout <<arr[i] <<" " ;
}
}

//driver program
int main()
{
int arr[] = {1 , 2 , 3 , 4 , 5 , 5 };
int n = sizeof (arr)/sizeof (arr[0]);
printTwoParts(arr, n);
return 0;
}``````

## Java

``````//java program to split an array
//into Two equal sum subarrays
import java.io.*;

class GFG {

//Returns split point. If not possible, then
//return -1.
static int findSplitPoint( int arr[], int n)
{

//traverse array element and compute sum
//of whole array
int leftSum = 0 ;

for ( int i = 0 ; i <n ; i++)
leftSum += arr[i];

//again traverse array and compute right
//sum and also check left_sum equal to
//right sum or not
int rightSum = 0 ;

for ( int i = n- 1 ; i>= 0 ; i--)
{
rightSum += arr[i];

//exclude current element to the left_sum
leftSum -= arr[i] ;

if (rightSum == leftSum)
return i ;
}

//if it is not possible to split array
//into two parts.
return - 1 ;
}

//Prints two parts after finding split
//point using findSplitPoint()
static void printTwoParts( int arr[], int n)
{
int splitPoint = findSplitPoint(arr, n);

if (splitPoint == - 1 || splitPoint == n )
{
System.out.println( "Not Possible" );
return ;
}
for ( int i = 0 ; i <n; i++)
{
if (splitPoint == i)
System.out.println();

System.out.print(arr[i] + " " );
}
}

//Driver program
public static void main (String[] args) {

int arr[] = { 1 , 2 , 3 , 4 , 5 , 5 };
int n = arr.length;

printTwoParts(arr, n);

}
}

//This code is contributed by vt_m``````

## Python3

``````# Python3 program to split
# an array into Two
# equal sum subarrays

# Returns split point.
# If not possible, # then return -1.
def findSplitPoint(arr, n) :
# traverse array element and
# compute sum of whole array
leftSum = 0
for i in range ( 0 , n) :
leftSum + = arr[i]

# again traverse array and
# compute right sum and also
# check left_sum equal to
# right sum or not
rightSum = 0
for i in range (n - 1 , - 1 , - 1 ) :
# to right_sum
rightSum + = arr[i]

# exclude current element
# to the left_sum
leftSum - = arr[i]

if (rightSum = = leftSum) :
return i

# if it is not possible
# to split array into
# two parts.
return - 1

# Prints two parts after
# finding split point
# using findSplitPoint()
def printTwoParts(arr, n) :
splitPoint = findSplitPoint(arr, n)

if (splitPoint = = - 1 or splitPoint = = n ) :
print ( "Not Possible" )
return

for i in range ( 0 , n) :
if (splitPoint = = i) :
print ("")
print (arr[i], end = " " )

# Driver Code
arr = [ 1 , 2 , 3 , 4 , 5 , 5 ]
n = len (arr)
printTwoParts(arr, n)

# This code is contributed by Manish Shaw
# (manishshaw1)``````

## C#

``````//C# program to split an array
//into Two equal sum subarrays
using System;

class GFG {

//Returns split point. If not possible, then
//return -1.
static int findSplitPoint( int []arr, int n)
{

//traverse array element and compute sum
//of whole array
int leftSum = 0;

for ( int i = 0 ; i <n ; i++)
leftSum += arr[i];

//again traverse array and compute right
//sum and also check left_sum equal to
//right sum or not
int rightSum = 0;

for ( int i = n-1; i>= 0; i--)
{
rightSum += arr[i];

//exclude current element to the left_sum
leftSum -= arr[i] ;

if (rightSum == leftSum)
return i ;
}

//if it is not possible to split array
//into two parts.
return -1;
}

//Prints two parts after finding split
//point using findSplitPoint()
static void printTwoParts( int []arr, int n)
{
int splitPoint = findSplitPoint(arr, n);

if (splitPoint == -1 || splitPoint == n )
{
Console.Write( "Not Possible" );
return ;
}
for ( int i = 0; i <n; i++)
{
if (splitPoint == i)
Console.WriteLine();

Console.Write(arr[i] + " " );
}
}

//Driver program
public static void Main (String[] args) {

int []arr = {1 , 2 , 3 , 4 , 5 , 5 };
int n = arr.Length;

printTwoParts(arr, n);

}
}

//This code is contributed by parashar``````

## PHP

``````<?php
//PHP program to split
//an array into Two
//equal sum subarrays

//Returns split point.
//If not possible, //then return -1.
function findSplitPoint( \$arr , \$n )
{
//traverse array element and
//compute sum of whole array
\$leftSum = 0;
for ( \$i = 0 ; \$i <\$n ; \$i ++)
\$leftSum += \$arr [ \$i ];

//again traverse array and
//compute right sum and also
//check left_sum equal to
//right sum or not
\$rightSum = 0;
for ( \$i = \$n - 1; \$i>= 0; \$i --)
{
//to right_sum
\$rightSum += \$arr [ \$i ];

//exclude current element
//to the left_sum
\$leftSum -= \$arr [ \$i ] ;

if ( \$rightSum == \$leftSum )
return \$i ;
}

//if it is not possible
//to split array into
//two parts.
return -1;
}

//Prints two parts after
//finding split point
//using findSplitPoint()
function printTwoParts( \$arr , \$n )
{
\$splitPoint = findSplitPoint( \$arr , \$n );

if ( \$splitPoint == -1 or
\$splitPoint == \$n )
{
echo "Not Possible" ;
return ;
}
for ( \$i = 0; \$i <\$n ; \$i ++)
{
if ( \$splitPoint == \$i )
echo "\n" ;
echo \$arr [ \$i ] , " " ;
}
}

//Driver Code
\$arr = array (1, 2, 3, 4, 5, 5);
\$n = count ( \$arr );
printTwoParts( \$arr , \$n );

//This code is contributed by anuj_67.
?>``````

``````1 2 3 4
5 5``````