1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
4
  • $\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 '18 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$ – Yuval Filmus Nov 8 '18 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 '18 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$ – Yuval Filmus Nov 10 '18 at 4:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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