#
Positive Subset Sum

/********************************************************************* * 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)); } } }