Going from the O(2^(N/2) N) algorithm described in the wikipedia article to O(2^(N/2)) just involves keeping the lists of subset sums sorted during the construction process, thereby avoiding the need for the expensive sorting step.
That said, the O(2^(N/2)) algorithm requires O(2^(N/2)) space, making it less than ideal; in most circumstances, an algorithm which generates the lists of subset sums for each half of the list on-demand using a priority queue is better -- this approach takes O(2^(N/2) N) time, but only O(2^(N/4)) memory.
Going from the O(2^(N/2) N) algorithm described in the wikipedia article to O(2^(N/2)) just involves keeping the lists of subset sums sorted during the construction process, thereby avoiding the need for the expensive sorting step.
That said, the O(2^(N/2)) algorithm requires O(2^(N/2)) space, making it less than ideal; in most circumstances, an algorithm which generates the lists of subset sums for each half of the list on-demand using a priority queue is better -- this approach takes O(2^(N/2) N) time, but only O(2^(N/4)) memory.