# Subset Sum with Endless Suppliesby Isai Damier, Android Engineer @ Google

```/*********************************************************************
* Author: Isai Damier
* Title: Subset Sum with Endless Supplies
* Project: geekviewpoint
* Package: algorithms
*
* Statement:
*   Given a sequence S, with n positive numbers totaling to T, check
*   whether there exists a subsequence totaling to x, where x is less
*   than or equal to T. You may use any of the elements in S more than
*   once.
*
* Time-complexity: pseudo-polynomial: O(n*x)
* Space-complexity: O(x)
*
* Dynamic Programming Strategy:
*
*   We are not going to say too much here since this is essentially the
*   "Positive Subset Sum" problem. So we will wait right here as you
*   go read the "Positive Subset Sum" implementation.
*
*   Okay. So there is one distinction between the two problems: here you
*   may use each elements as many times as you need. So given the sequence
*   S={2,8,24}, we can reach 6 as 2+2+2 or 20 as 8+8+2+2.
*
*   To achieve this multiplicity, all we have to change is the direction
*   of the nested for-loop so that we end up with:
*
*     for(int e : S)
*       for(int i=0; i<=x; i++)
*         if(sum[i])
*           sum[i+e]=true;
*
*   The reason it's that simple is because the line "if(sum[i])" is
*   most of the time looking at multiples. For instance, during the first
*   pass of the outer for-loop (i.e. e=2), the second for-loop sets all
*   multiples of 2 to true. Manually run the example where S={2,8,24}
*   and x=18 if you still don't see it.
**********************************************************************/
package algorithm.programming.dynamic;

public class SubsetSumWithMultipleSupplies {

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

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

public class SubsetSumWithMultipleSuppliesTest {

/**
* Test of subsetSumEndlessReuse method,
* of class SubsetSumWithMultipleSupplies.
*/
@Test
public void testPositiveSubsetSum() {
System.out.println("subsetSumEndlessReuse");
int[] S = {2, 8, 24};
SubsetSumWithMultipleSupplies instance = new SubsetSumWithMultipleSupplies();
for (int x = 24 + 8 + 2; x >= 0; x = -2) {
assertTrue(instance.subsetSumEndlessReuse(S, x));
}
for (int x = 24 + 8 + 2 - 1; x >= 1; x = -2) {
assertFalse(instance.subsetSumEndlessReuse(S, x));
}
}
}```