Array equal sum partition

Problem

Partition an integer array in two parts such that sum of each parts are same. The elements need not to be contiguous.

Brute force

If we try to find out all the subsets of the set it is of the order 2^n. For each of this subset we will have to find the sum and check it with the half of the total sum. So the total complexity will become O(n*2^n)

Better Solution

The sum of two parts should be equal. That means sum should be equal to half of total sum. As they are all integers so if the sum is odd number then it is not possible to partition. If they are even we will try to find whether that half of sum is possible by adding numbers from the array. We solve this by dynamic programming. We take a two dimensional array L of size count+1, sum/2+1. Where L[i,j]=maximum sum possible with elements of array 0 to i and sum not exceeding j. We compute this array from L[0,0] to L[n,sum/2]. So for computing L[i,j] we need to check the element i. if it is greater than j then it cannot be included in the sum so L[i,j]=L[i-1,j]. If ith element is less than j, then we should consider two cases and take the greater of them. First case is where we don't include the element in sum. Then L[i,j] = L[i-1,j] which is exactly like before. Now if we include the element, then L[i,j]=a[i]+L[i-1,j-a[i]]. In this way we fill this 2-d array. If L[n,sum/2] is equal to sum/2 that means the array can be partitioned in two parts whose sums are equal. Then we find out which elements have been included in that sum by backtracking through that 2-d array.

For backtracking through the array we just apply the reverse logic. If L[i,j] is equal to a[i]+L[i-1,j-a[i]] then that element is included in the partition. Then we continue this process to L[i-1,j-a[i]). If it is not equal then the element is not included in the final sum, so we proceed to L[i-1,j] After we get the complete list of elements in a partition we remove them from the original array to get the second partition. 

Code

import java.util.ArrayList;
import java.util.List;

public class EqualSumPartition
{
 public static void main(String[] args)
 {
  Integer[] arr ={ 1, 2, 3, 6, 4, 5, 7 };
  System.out.println("Original Array");
  for (Integer num : arr)
  {
   System.out.print(num + ", ");
  }
  System.out.println();

  Integer[][] parts = partition(arr);
  if (parts == null)
  {
   System.out.println("partition not possible");
   return;
  }
  System.out.println("partition");
  for (Integer num : parts[0])
   System.out.print(num + ", ");
  System.out.println();
  for (Integer num : parts[1])
   System.out.print(num + ", ");
 }

 private static Integer[][] partition(Integer[] arr)
 {
  List < integer > list = new ArrayList < integer >();
  List < integer > part = new ArrayList < integer >();

  int sum = 0;
  for (Integer num : arr)
  {
   list.add(num);
   sum += num;
  }
  if (sum % 2 == 1)
   return null;
  sum /= 2;
  int[][] memo = new int[arr.length + 1][sum + 1];
  for (int i = 1; i <= arr.length; ++i)
  {
   for (int s = 1; s <= sum; ++s)
   {
    if (arr[i - 1] > s
      || memo[i - 1][s] > arr[i - 1]
        + memo[i - 1][s - arr[i - 1]])
     memo[i][s] = memo[i - 1][s];
    else
    {
     memo[i][s] = arr[i - 1] + memo[i - 1][s - arr[i - 1]];
    }
   }
  }
  if (memo[arr.length][sum] != sum)
   return null;
  int i = arr.length;
  int s = sum;
  while (s > 0 && i > 0)
  {
   if (arr[i - 1] <= s
     && memo[i][s] == arr[i - 1] + memo[i - 1][s - arr[i - 1]])
   {
    part.add(arr[i - 1]);
    s = s - arr[i - 1];
   }
   i--;
  }
  for (Integer num : part)
   list.remove(num);
  Integer[][] result = new Integer[2][];
  result[0] = part.toArray(new Integer[] {});
  result[1] = list.toArray(new Integer[] {});
  return result;
 }

}