Thursday, April 16, 2015

Array partition problem

Problem: Determine whether a given array can be partitioned into two arrays such that the sum of elements in both arrays is same.

Solution: 

It can be solved using Subset sum problem. Following are the two main steps to solve this problem using subset sum problem:
  1. Calculate sum of the array. If sum is odd, there can not be two subsets with equal sum.
  2. If sum of array elements is even, solve subset sum problem for this array with sum equal to sum/2.
Implementation:

bool canBePartitioned(int *arr, int len)
{
if(arr == NULL)
return true;
int sum = 0;
for(int i = 0; i < len; ++i)
sum += arr[i];
if(sum == 0)
return true;
if(sum %2 != 0)
return false;
return isSubsetSum(arr, len, sum/2);
}

Please find the implementation of Subset sum at the following URL:

Complexity: O(n2)

No comments:

Post a Comment