The Partition Problem
by Isai Damier

/*********************************************************************
 * Author: Isai Damier
 * Title: Subset Sum: Divide Candies Evenly
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Given n bags of candies, divide the candies between two kids
 *   as evenly as possible without splitting individual bags. The candies
 *   are valued by weight, in ounce (oz).
 *
 * Time Complexity: O(n*w)
 *    where w is the total weight of all the candies together.
 * 
 * Dynamic Programming Strategy:
 * 
 *   The difference between this problem and the "Positive Subsequence
 *   Sum [make hyperlink]" problem is that here, instead of solving for a given weight
 *   x, we are ask to come up with x given the constraint that x must
 *   be as close to T/2 as possible. 
 * 
 *   So let's do this. Instead of wasting too much time thinking about x,
 *   let x = T/2 so that we can proceed as we did for the "Positive
 *   Subsequence Sum" problem. Then after we are done filling sum{}
 *   completely, we will walk the array backward until we find a positive
 *   weight. For our illustration, we will use sequence S={2,4,7,9}.
 *   Here are the steps:
 * 
 *   0] Create a boolean array called sum of size x+1:
 *     As you might guess, when we are done filling the array, all the
 *     sub-sums between 0 and x that can be calculated from S will be
 *     set to true and those that cannot be reached will be set to false.
 *     For example if S={2,4,7,9} then sum[5]=false while sum[13]=true
 *     because 4+9=13.
 * 
 *   1] Initialize sum{} to false:
 *      Before any computation is performed, assume/pretend that each
 *      sub-sum is unreachable. We know that's not true, but for now
 *      let's be outrageous.
 * 
 *   2] Set sum at index 0 to true:
 *     This truth is self-evident. By taking no elements from S, we end
 *     up with an empty sub-sequence. Therefore we can mark sum[0]=true,
 *     since the sum of nothing is zero.
 * 
 *   3] To fill the rest of the array, we are going to use the following
 *     trick. Starting with 0, each time we find a positive sum, we will
 *     add an element from S to that sum to get a greater sum. For example,
 *     since sum[0]=true and 2 is in S, then sum[0+2] must also be true.
 *     Therefore, we set sum[0+2]=sum[2]=true. Then from sum[2]=true and
 *     element 4, we can say sum[2+4]=sum[6]=true, and so on.
 * 
 *   4] Recall that we decided to let x=T/2. In an ideal world, we will
 *    split the candies and the kids will get exactly the same amount.
 *    But since that's not likely to happen in real life, here is a 
 *    sensible strategy. After we finish filling the sum{} array, starting
 *    at x=T/2 we will check to see if sum[x] equals true. If it is, we
 *    are done. If not, we decrease x by one and keep check, until we
 *    find sum[x]==true.
 * 
 **********************************************************************/ 
 package algorithm.programming.dynamic;

public class CandyToKids {

  public int[] subsetSumDivideByTwo(int[] S) {
    //preliminary
    int T = 0;
    for (int a : S) {
      T += a;
    }

    int x = T / 2 + 1;

    boolean weight[] = new boolean[x + 1];
    weight[0] = true;
    for (int a : S) {
      for (int i = x; i >= a; i--) {
        if (!weight[i] && weight[i - a]) {
          weight[i] = true;
        }
      }
    }
    for (int i = x; i >= 0; i--) {
      if (weight[i]) {
        return new int[]{i, T - i};
      }
    }
    return null;//unreachable but needed for java.
  }
}
package algorithm.programming.dynamic;

import org.junit.Test;
import static org.junit.Assert.*;

public class CandyToKidsTest {

  /**
   * Test of subsetSumDivideByTwo method, of class CandyToKids.
   */
  @Test
  public void testSubsetSumDivideByTwo() {
    System.out.println("subsetSumDivideByTwo");

    CandyToKids instance = new CandyToKids();

    int[] S = {3, 5, 7, 8, 11, 13, 17, 21, 34};
    int[] expResult = {60, 59};
    int[] result = instance.subsetSumDivideByTwo(S);
    assertArrayEquals(expResult, result);

    S = new int[]{3, 5, 7, 8, 13, 17, 21, 34};
    expResult = new int[]{55, 53};
    result = instance.subsetSumDivideByTwo(S);
    assertArrayEquals(expResult, result);

    S = new int[]{11, 29, 37, 45, 59, 67, 89, 97, 37};
    expResult = new int[]{234, 237};
    result = instance.subsetSumDivideByTwo(S);
    assertArrayEquals(expResult, result);
  }
}