Find if array can be divided into two subarrays of equal sum if any one element can be deleted

5
votes

Given a array of numbers find if there is a way to delete/remove a number from the array and make one partition in the array( dividing the array into two subarrays ) such that sum of elements in subarray1 is equal to sum of elements in subarray2.

A subarray is a contiguous part of array.
Array [1, 2, 3, 4] has (1), (1,2), (2,3,4),(1,2,3,4) etc.. as its subarrays but not (1,3) , (2,4) , (1,3,4), etc..

Now let us consider one example:-

(Follow 0-based indexing )
Array[] = [ 6, 2, 2, 1, 3 ]

Possible solutions
Delete Array[0] => updated array: - [ 2,2,1,3 ]
Possible partition              : - [2,2] and [3,1] where (2+2) = (3+1) = 4
or
Delete Array[1] => updated array: - [ 6,2,1,3 ]
Possible partition              : - [6] and [2,1,3] where (6) = (2+1+3) = 6
or
Delete Array[2] => updated array: - [ 6,2,1,3 ]
Possible partition              : - [6] and [2,1,3] where (6) = (2+1+3) = 6

Now a similar question already exists where we just have to, find if array can be divided into two subarrays of equal sum , can be done in O(n) =>

PsuedoCode:- The efficient solution involves calculating sum of all elements of the array in advance. Then for each element of the array, we can calculate its right sum in O(1) time by using total sum of the array elements minus sum of elements found so far. The time complexity of this solution would be O(n) and auxiliary space used by it will be O(1).

So to solve our problem one brute force method is:- remove every element once and check if the array can be divided into two subarrays of equal sum. Thus it will require O(n^2) time.

So can we do better than this time complexity?

1
arraysalgorithmsub-array

1 Answers

0
votes

At first calculate sum of array and check for every valid pivote (1->len -1) if the leftSum is equal to rightSum and update them each step! This method returns the pivot if it does exist othewise -1.

int findPartitionPivot(const vector<int> &input){
    if(input.size() <= 3)
        return -1;

    int sum = 0;
    for(int i = 0; i < input.size(); i++)
        sum += input[i];

    int leftSum = input[0];
    int rightSum;

    for(int pivotIndex = 1; pivotIndex < input.size() - 1; pivotIndex ++)
    {
        rightSum = sum -  leftSum - input[pivotIndex];
        if(rightSum == leftSum)
            return pivotIndex;
        leftSum += input[pivotIndex];
    }
    return -1;
}