A better exponential time algorithm is known which runs in time formula_12. The algorithm splits arbitrarily the formula_7 elements into two sets of formula_14 each. For each of these two sets, it stores a list of the sums of all formula_15 possible subsets of its elements. Each of these two lists is then sorted. Using a standard comparison sorting algorithm for this step would take time formula_16. However, given a sorted list of sums for formula_17 elements, the list can be expanded to two sorted lists with the introduction of a (formula_18)th element, and these two sorted lists can be merged in time formula_19. Thus, each list can be generated in sorted form in time formula_12. Given the two sorted lists, the algorithm can check if an element of the first array and an element of the second array sum up to formula_21 in time formula_12. To do that, the algorithm passes through the first array in decreasing order (starting at the largest element) and the second array in increasing order (starting at the smallest element). Whenever the sum of the current element in the first array and the current element in the second array is more than formula_21, the algorithm moves to the next element in the first array. If it is less than formula_21, the algorithm moves to the next element in the second array. If two elements that sum to formula_21 are found, it stops. Horowitz and Sahni first published this algorithm in a technical report in 1974. The problem can be solved in pseudo-polynomial time using dynamic programming. Suppose the sequence is   sorted in the increasing order and we wish to determine if there is a nonempty subset which sums to zero. Define the boolean-valued function formula_27 to be the value (formula_28 or formula_29) of  Thus, the solution to the problem "Given a set of integers, is there a non-empty subset whose sum is zero?" is the value of formula_32. Let formula_33 be the sum of the negative values and formula_34 the sum of the positive values. Clearly, formula_35, if formula_36 or formula_37. So these values do not need to be stored or computed. Create an array to hold the values formula_27 for formula_39 and formula_40. The array can now be filled in using a simple recursion. Initially, for formula_40, set  where formula_43 is a boolean function that returns true if formula_44 is equal to formula_21, false otherwise.