Split an Array into Two Equal Sum Subarrays

Given an array of integers arr[], determine whether it is possible to split it into two contiguous subarrays (without reordering the elements) such that the sum of the two subarrays is equal.

Input : arr[] = [ 1 , 2 , 3 , 4 , 5 , 5]
Output : True
Explanation :The array can be divided after index 3 into two subarrays: [1, 2, 3, 4] and [5, 5].

Input : arr[] = [ 4, 3, 2, 1]
Output : False
Explanation: No possible split gives equal sum.

Try it on GfG Practice

Table of Content

[Naive Approach] Using Nested Loop - O(n^2) Time and O(1) Space
[Expected Approach] Running Prefix Sum and Suffix Sum - O(n) Time and O(1) Space

[Naive Approach] Using Nested Loop - O(n²) Time and O(1) Space

Use two loops where the outer loop determines the split position, and the inner loops compute the sum of the left part (including the current index) and the right part (excluding the current index). If the two sums are equal, a valid partition is found.

C++

//Driver Code Starts
#include <vector>
using namespace std;

//Driver Code Ends

bool canSplit(vector<int> &arr)
{
    int n = arr.size();

    // total sum
    long total = 0;
    for (int i = 0; i < n; i++)
        total += arr[i];

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

        // right sum
        long rightSum = total - leftSum;

        // Check the condition
        if (leftSum == rightSum)
            return true;
    }

    return false;
}

//Driver Code Starts

int main()
{
    vector<int> arr = {1, 2, 3, 4, 5, 5};

    if (canSplit(arr))
        cout << "True" << endl;
    else
        cout << "False" << endl;

    return 0;
}
//Driver Code Ends

Java

//Driver Code Starts
import java.util.ArrayList;
import java.util.Arrays;

public class GFG {

//Driver Code Ends

    public static boolean canSplit(ArrayList<Integer> arr)
    {
        int n = arr.size();

        // total sum
        long total = 0;
        for (int i = 0; i < n; i++)
            total += arr.get(i);

        long leftSum = 0;
        for (int i = 0; i < n; i++) {
            leftSum += arr.get(i);

            // right sum
            long rightSum = total - leftSum;

            // Check the condition
            if (leftSum == rightSum)
                return true;
        }

        return false;
    }

//Driver Code Starts

    public static void main(String[] args)
    {
        ArrayList<Integer> arr = new ArrayList<>(
            Arrays.asList(1, 2, 3, 4, 5, 5));

        if (canSplit(arr))
            System.out.println("True");
        else
            System.out.println("False");
    }
}
//Driver Code Ends

Python

def canSplit(arr):
    total = sum(arr)
    leftSum = 0

    for num in arr:
        leftSum += num
        rightSum = total - leftSum

        # Check the condition
        if leftSum == rightSum:
            return True

    return False


#Driver Code Starts

if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5, 5]

    if canSplit(arr):
        print("True")
    else:
        print("False")

#Driver Code Ends

//Driver Code Starts
using System;
using System.Collections.Generic;

class GFG {

//Driver Code Ends

    public static bool canSplit(List<int> arr)
    {
        int n = arr.Count;

        // total sum
        long total = 0;
        for (int i = 0; i < n; i++)
            total += arr[i];

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

            // right sum
            long rightSum = total - leftSum;

            // Check the condition
            if (leftSum == rightSum)
                return true;
        }

        return false;
    }

//Driver Code Starts

    static void Main()
    {
        List<int> arr = new List<int>{ 1, 2, 3, 4, 5, 5 };

        if (canSplit(arr))
            Console.WriteLine("True");
        else
            Console.WriteLine("False");
    }
}
//Driver Code Ends

JavaScript

function canSplit(arr)
{
    let total = arr.reduce((a, b) => a + b, 0);
    let leftSum = 0;

    for (let num of arr) {
        leftSum += num;
        let rightSum = total - leftSum;

        // Check the condition
        if (leftSum === rightSum)
            return true;
    }

    return false;
}


//Driver Code Starts
// driver code
const arr = [ 1, 2, 3, 4, 5, 5 ];

if (canSplit(arr))
    console.log("True");
else
    console.log("False");
//Driver Code Ends

Output

True

[Expected Approach] Running Prefix Sum and Suffix Sum - O(n) Time and O(1) Space

First, compute the total sum of the array. Then traverse from left to right, maintaining a running left sum. At each step, subtract the left sum from the total sum to obtain the right sum.

C++

//Driver Code Starts
#include <vector>
using namespace std;

//Driver Code Ends

bool canSplit(vector<int> &arr)
{
    int n = arr.size();

    // total sum
    long total = 0;
    for (int i = 0; i < n; i++)
        total += arr[i];

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

        // right sum
        long rightSum = total - leftSum;

        // Check the condition
        if (leftSum == rightSum)
            return true;
    }

    return false;
}

//Driver Code Starts

int main()
{
    vector<int> arr = {1, 2, 3, 4, 5, 5};

    if (canSplit(arr))
        cout << "True" << endl;
    else
        cout << "False" << endl;

    return 0;
}
//Driver Code Ends