less space - . Rather than generating and storing all subsets of n/2 elements in advance, they partition the elements into 4 sets of n/4 elements each, and generate subsets of n/2 element pairs dynamically using a min heap, which yields the above time and space complexities since this can be done in and space given 4 lists of length k. Due to space requirements, the HS algorithm is practical for up to about 50 integers, and the SS algorithm is practical for up to 100 integers. Howgrave-Graham and Joux Howgrave-Graham and Joux presented a probabilistic algorithm that runs faster than all previous ones - in time using space . It solves only the decision problem, cannot prove there is no solution for a given sum, and does not return the subset sum closest to T. The techniques of Howgrave-Graham and Joux were subsequently extended bringing the time-complexity to . Pseudo-polynomial time dynamic programming solutions SSP can be solved in pseudo-polynomial time using dynamic programming. Suppose we have the following sequence of elements in an instance: We define a state as a pair (i, s) of integers. This state represents the fact that "there is a nonempty subset of which sums to ." Each state (i, s) has two next states: (i+1, s), implying that is not included in the subset; (i+1, s+), implying that is included in the subset. Starting from the initial state (0, 0), it is possible to use any graph search algorithm (e.g. BFS) to search the state (N, T). If the state is found, then by backtracking we can find a subset with a sum of exactly T. The run-time of this algorithm is at most linear in the number of states. The number of states is at most N times the number of different possible sums. Let be the sum of the negative values and the sum of the positive values; the number of different possible sums is at most B-A, so the total runtime is in . For example, if all input values are positive and bounded by some constant C, then B is at most N C, so the time required is . This solution does not count as polynomial time in complexity theory because is not polynomial in the size of the problem, which is the number of bits used to represent it. This algorithm is polynomial in the values of