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 1


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). $$

  • $\begingroup$ 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? $\endgroup$
    – C Shreve
    Nov 8, 2018 at 21:01
  • $\begingroup$ We’re not using mergesort at all, only the linear time merge subroutine. The output array $A_m$ is already sorted. $\endgroup$ Nov 8, 2018 at 21:28
  • $\begingroup$ 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})$ $\endgroup$
    – C Shreve
    Nov 10, 2018 at 4:42
  • $\begingroup$ 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. $\endgroup$ Nov 10, 2018 at 4:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.