Check if array can be divided in two parts with equal sum

Given an array of integers, write a function that returns true if it can be divided in two parts having equal sum. For example:

If Input array is {10, 20 , 30 , 5 , 40 , 50 , 40 , 15}
Output: true
Divide the array in two parts {0, 20, 30, 5, 40} and {50, 40, 15} both having sum = 105.

If Input array is {10, 20, 30, 5, 40, 50, 40, 10}
Output: False
Array cannot be divided in two parts having same sum.

Solution:

One check is simple. If sum of all the elements of the array is odd then it cannot be divided in two parts with equal sum.

But, when the total sum of array is even (say, totalSum), then we have to check if we can find a subset of array with sum= totalSum/2. This is the challenging part. So our problem reduces to:

Find the subset of array with sum = totalSum/2

Recursive Solution:

If subsetSumExist is a function that returns true if subset of array ‘arr’ exist with sum = totalSum.

bool subsetSumExist(int* arr, int n, int totalSum)

Then the problem can be solved recursively by dividing it in two parts

1. Consider current element (first one) as part of the array
2. Consider current element as not part of the array.

If any of the two sub-problems return true, this function also return true. Else it return false. Below is the code for the same.

bool subsetSumExist(int* arr, int n, int sum)
{
    if(sum == 0)
        return true;
    if(n == 0)
        return false;
    return subsetSumExist(arr, n-1, sum-arr[0]) || subsetSumExist(arr, n-1, sum);
}
bool twoPartsExists(int* arr, int n)
{
    int totalSum = 0;
    for(int i=0; i<n; i++)
        totalSum += arr[i];
    // if sum is odd then does not exist.
    if( (totalSum & 1) != 0)
        return false;
    return subsetSumExist(arr, n, totalSum/2);
}
int main()
{
	int arr[] = {10, 10, 20, 5, 5, 5, 5};
	cout<<"twoPartsExists :"<<twoPartsExists(arr, 7);
	return 0;
}

Above solution takes exponential time (O(2ⁿ)). And since it maq be solving a sub-problem more, there is a scope of using dynamic programming approach.

Dynamic Programming approach 
In this approach we solve the problem in bottom-up fashion. Let’s create a 2-dim array of size (totalSum/2)*(n+1) and try to fill each entry as shown below:

bool twoPartsExistsDyn(int *arr, int n)
{
    int totalSum = 0, i;
    for(i=0; i<n; i++)
        totalSum += arr[i];
    // if sum is odd then does not exist.
    if( (totalSum & 1) != 0)
        return false;
    // Sum of each part.
    int partSum = totalSum/2;
    // latest compilers allows variable length arrays.
    // Else declare the array on heap
    bool partArr[partSum+1][n+1];
    // initialize top row as true
    for (i = 0; i <= n; i++)
        partArr[0][i] = true;
    // initialize first column as false (except part[0][0])
    for (i = 1; i <= partSum; i++)
        partArr[i][0] = false;
    // Fill the partition table in botton up manner
    for (i = 1; i <= partSum; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            partArr[i][j] = partArr[i][j-1];
            if (i >= arr[j-1])
                partArr[i][j] = partArr[i][j] || partArr[i - arr[j-1]][j-1];
        }
    }
    return partArr[partSum][n];
}

Read more about it here…