We are looking for beta users for our new mobile app Prefies (pref-ies).
To participate, go to prefies.com and use access code “GeekViewpoint”.
This is a pre-release sneak-peak for Geekviewpoint users only!

Positive Subset Sum
by Isai Damier

/*********************************************************************
 * Author: Isai Damier
 * Title: Positive Subset Sum
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Given a sequence of n positive numbers totaling to T, check
 *   whether there exists a subsequence totaling to x, where x is less
 *   than or equal to T.
 *
 * Time-complexity: pseudo-polynomial: O(n*x)
 * Space-complexity: O(x)
 * 
 * Dynamic Programming Strategy:
 * 
 *   Let's call the given Sequence S for convenience. Solving this
 *   problem, there are two approaches we could take. On the one hand,
 *   we could look through all the possible sub-sequences of S to see if
 *   any of them sum up to x. This approach, however, would take an
 *   exponential amount of work since there are 2^n possible
 *   sub-sequences in S. On the other hand, we could list all the sums
 *   between 0 and x and then try to find a sub-sequence for each one
 *   of them until we find one for x. This second approach turns out to
 *   be quite a lot faster: O(n*T). 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
 *     since 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 table, we are going to use the following
 *     trick. Let S={2,4,7,9}. Then 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.
 * 
 *  Step 3 is known as the relaxation step. First we started with an
 *  absurd assumption that no sub-sequence of S can sum up to any
 *  number. Then as we find evidence to the contrary, we relax our
 *  assumption.
 * 
 * Alternative implementation: 
 *   This alternative is easier to read, but it does not halt for small x.
 *   In the actual code, each for-loop checks for "!sum[x]" since that's
 *   really all we care about and should stop once we find it. Also
 *   this time complexity is of O(n*T) and space complexity is O(T)
 * 
 *   boolean sum[] = new boolean[T + 1];
 *   sum[0] = true;
 *   for (int a : A)
 *     for (int i = T; i >= a; i--)
 *       if (!sum[i] && sum[i - a])
 *         sum[i] = true;
 * 
 **********************************************************************/ 
 package algorithm.programming.dynamic;

public class PositiveSubsequenceSum {

  public boolean positiveSubsetSum(int[] A, int x) {
    //preliminary
    int T = 0;
    for (int a : A) {
      T += a;
    }
    if (x < 0 || x > T) {
      return false;
    }
    //algorithm
    boolean sum[] = new boolean[x + 1];
    sum[0] = true;
    for (int p = 0; !sum[x] && p < A.length; p++) {
      int a = A[p];
      for (int q = x; !sum[x] && q >= a; q--) {
        if (!sum[q] && sum[q - a]) {
          sum[q] = true;
        }
      }
    }
    return sum[x];
  }
}
package algorithm.programming.dynamic;

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

public class PositiveSubsequenceSumTest {

  public PositiveSubsequenceSumTest() {
  }

  /**
   * Test of positiveSubsetSum method, of class PositiveSubsequenceSum.
   */
  @Test
  public void testPositiveSubsetSum() {
    System.out.println("positiveSubsetSum");
    int[] S = {3, 5, 6};
    PositiveSubsequenceSum instance = new PositiveSubsequenceSum();
    
    int xTrue[] = {0, 3, 5, 6, 8, 9, 11, 14};
    for (int x : xTrue) {
      assertTrue(instance.positiveSubsetSum(S, x));
    }

    int xFalse[] = {1, 2, 4, 7, 10, 12, 13};
    for (int x : xFalse) {
      assertFalse(instance.positiveSubsetSum(S, x));
    }
  }
}
Phuzz! Turn your photo into a puzzle!