Let $S(X) = \{\sum_{i\in Y} i | Y\subset X \}$, the set of subset sums of $X$. $S_n(X) = S(X)\cap \{1,\ldots,n\}$. Consider the following variant of subset sum.

INPUT: positive integer $n$ and set $X\subset \{1,\ldots,n\}$.
OUTPUT: $S_n(X)$

There is the common dynamic programming algorithm taught in algorithm classes, which takes $O(n |X|)$ time. It takes $O(n^2)$ time for large input sets. It's not hard to devise and output sensitive version that takes $O(|X||S_n(X)|+n)$ time.

It's possible to solve it in $O((n \log n)^\frac{3}{2})$ time by decompose the problem to $\sqrt{n\log n}$ ALL-SUBSET-SUMS with small output size, and we can combine the solutions through FFT.

How fast can we solve this problem? There are subset sum algorithms using analytical number theory[1], but they have many technical conditions on the input. It can't be applied directly on ALL-SUBSET-SUMS.


[1] M. Chaimovich , G. Freiman , Z. Galil, Solving dense subset-sum problems by using analytical number theory, Journal of Complexity, v.5 n.3, p.271-282, Sept. 1989

  • $\begingroup$ Why pseudo-polynomial? $\endgroup$ – Saeed Mar 14 '14 at 10:04
  • $\begingroup$ Because there is no polynomial time algorithm for this problem. We can find $|X|=O(\log n)$ and $|S_n(X)| = \Omega(n)$. The output alone takes exponential time with respect to the input size. $\endgroup$ – Chao Xu Mar 14 '14 at 19:53
  • $\begingroup$ I see, I thought may be |X| is in $\Omega(n)$. $\endgroup$ – Saeed Mar 14 '14 at 22:54

Your Answer

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

Browse other questions tagged or ask your own question.