# Partition an array into two subarrays with the same sum

Posted in

Vinay Khatri
Last updated on September 28, 2022

## Problem

Given an array of integers greater than zero, find if it is possible to split it into two subarrays such that the sum of the two subarrays is the same.

#### Sample Input

`[1,2,3,6]`

#### Sample Output

```[1,2,3]
[6]```

### Approach

An optimal solution is to first compute the sum of the entire array. Now we traverse the array from the right and keep track of the right sum, left sum can be computed by subtracting the current element from the whole sum. This approach takes O(N) time.

#### C++ Programming

```#include<bits/stdc++.h>
using namespace std;

int findPoint(int arr[], int n)
{

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

prefixSum -= arr[i] ;

if (suffixSum == prefixSum)
return i ;
}
return -1;
}

void solve(int arr[], int n)
{
int splitPoint = findPoint(arr, n);

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

int main()
{
int arr[] = {1 , 2 , 3 , 6 };
int n = sizeof(arr)/sizeof(arr[0]);
solve(arr, n);
return 0;
}
```

Output

```1 2 3
6```

C Programming

```#include<stdio.h>

int findPoint(int arr[], int n)
{
int prefixSum = 0;
for (int i = 0 ; i < n ; i++)
prefixSum += arr[i];
int suffixSum = 0;
for (int i=n-1; i >= 0; i--)
{
suffixSum += arr[i];

prefixSum -= arr[i] ;

if (suffixSum == prefixSum)
return i ;
}
return -1;
}

void solve(int arr[], int n)
{
int splitPoint = findPoint(arr, n);

if (splitPoint == -1 || splitPoint == n )
{
printf("Cannot split");
return;
}
for (int i = 0; i < n; i++)
{
if(splitPoint == i)
printf("\n");
printf("%d ",arr[i]);
}
}

int main()
{
int arr[] = {1 , 2 , 3 , 6 };
int n = sizeof(arr)/sizeof(arr[0]);
solve(arr, n);
return 0;
}```

Output

```1 2 3
6```

#### Python Programming

```def findPoint(arr, n) :
prefixSum = 0
for i in range(0, n) :
prefixSum += arr[i]
suffixSum = 0
for i in range(n-1, -1, -1) :

suffixSum += arr[i]

prefixSum -= arr[i]

if (suffixSum == prefixSum) :
return i
return -1

def solve(arr, n) :
splitPoint = findPoint(arr, n)

if (splitPoint == -1 or splitPoint == n ) :
print ("cannot Split")
return

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

arr = [1, 2, 3, 6]
n = len(arr)
solve(arr, n)```

Output

```1 2 3
6```