# Subset sum exponential solution - how does the sorting work?

The wiki for the subset sum problem found here it states that you take the list of N elements and split it into two lists of N/2 elements. You then generate all the subsets for each list (each having $$2^{N/2}$$ subsets). It then states...

"Each of these two lists is then sorted. Using a standard comparison sorting algorithm for this step would take time $$O(2^{N/2}N)$$. However, given a sorted list of sums for k elements, the list can be expanded to two sorted lists with the introduction of a (k + 1)st element, and these two sorted lists can be merged in time $$O(2^{k})$$."

Can someone illustrate/explain this part of the algorithm?

## 1 Answer

The idea is that two sorted lists of length $$n$$ can be merged into one sorted list of length $$2n$$ in time $$O(n)$$. This is a standard procedure used in the mergesort algorithm. Given a list of integers $$x_1,\ldots,x_m$$, you proceed as follows:

• Start with $$A_0 = 0$$.
• Merge $$A_0$$ and $$A_0 + x_1$$ into $$A_1$$.
• Merge $$A_1$$ and $$A_1 + x_2$$ into $$A_2$$.
• ...
• Merge $$A_{m-1}$$ and $$A_{m-1} + x_m$$ into $$A_m$$.
• Output $$A_m$$.

Here $$A_k + x_{k+1}$$ is formed by adding $$x_{k+1}$$ to all elements of $$A_k$$, preserving the order.

Since $$A_k$$ has length $$2^k$$, the total running time is $$O(|A_0| + |A_1| + \cdots + |A_{m-1}|) = O(1 + 2 + \cdots + 2^{m-1}) = O(2^m).$$

• What seems unclear is not the merging but the sorting. To sort a list with N elements (using mergesort) requires N $\log_2(N)$ steps. We have $2^{N/2}$ elements (in each list). Wouldn't performing merge sort on these elements take $2^{N/2}\log_2(2^{N/2})$ = $2^{N/2}*N/2$ steps? This would imply a runtime of $O(2^{N/2}N)$ would it not? – C Shreve Nov 8 '18 at 21:01
• We’re not using mergesort at all, only the linear time merge subroutine. The output array $A_m$ is already sorted. – Yuval Filmus Nov 8 '18 at 21:28
• I understand that merging 2 sorted lists of size N is O(N) but how do the lists (each of length $2^{N/2}$) get sorted to begin with then? From the wiki article is seems like the algorithm A-takes list of N elements, breaks it into two lists of N/2 elements. B-generates all $2^{N/2}$ subsets for each list. C-sorts these lists (how?) . D-merges these lists (each with $2^{N/2}$ elements) in linear time...which in this case is $O(2^{N/2})$ – C Shreve Nov 10 '18 at 4:42
• I suggest ignoring Wikipedia and focusing on my answer, which describes explicitly the linear time algorithm that outputs the sorted list of all subset sums. – Yuval Filmus Nov 10 '18 at 4:52