Partition an array into two subarrays with the same sum

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

People are also reading:

• Rearrange an array such that arr[i] = i
• Minimum Edit Distance
• The Stock Span Problem
• Print Square Using * Character
• Diameter of a Binary Tree
• Bottom View of a Binary Tree
• Subset Sum Problem
• Maximum size square sub-matrices with all 1’s
• Subarray with Sum k
• Find Maximum Subarray Sum