<p>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.</p>

<blockquote>
  <p><strong>ALL-SUBSET-SUMS</strong>  <br />
  <strong>INPUT</strong>: positive integer $n$ and set $X\subset \{1,\ldots,n\}$.<br />
  <strong>OUTPUT</strong>: $S_n(X)$</p>
</blockquote>

<p>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.</p>

<p>It's possible to solve it <a href="http://www.chaoxuprime.com/posts/2014-02-26-subset-target-sum.html#the-algorithm-that-exploits-the-sparsity">in $O((n \log n)^\frac{3}{2})$ time</a> by decompose the problem to $\sqrt{n\log n}$ <strong>ALL-SUBSET-SUMS</strong> with small output size, and we can combine the solutions through FFT. </p>

<p>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 <strong>ALL-SUBSET-SUMS</strong>.</p>

<p><strong>Reference:</strong> </p>

<p>[1] M. Chaimovich , G. Freiman , Z. Galil, <a href="http://dl.acm.org/citation.cfm?id=68751&amp;CFID=300414753&amp;CFTOKEN=22641006">Solving dense subset-sum problems by using analytical number theory</a>, Journal of Complexity, v.5 n.3, p.271-282, Sept. 1989</p>

CC BY-SA 3.0
2014-03-14T10:04:23.440Z
Why pseudo-polynomial?
Saeed
CC BY-SA 3.0
2014-03-14T19:53:06.520Z
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.
Chao Xu
CC BY-SA 3.0
2014-03-14T22:54:44.430Z
I see, I thought may be |X| is  in $\Omega(n)$.
Saeed
<subset-sum>
Faster pseudo-polynomial time algorithm for subset-sum?
Chao Xu
# Faster pseudo-polynomial time algorithm for subset-sum?

(Asked by: username_0 on 2014-03-13)

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.

> **ALL-SUBSET-SUMS**   
> **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](http://www.chaoxuprime.com/posts/2014-02-26-subset-target-sum.html#the-algorithm-that-exploits-the-sparsity) 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**.

**Reference:**

[1] M. Chaimovich , G. Freiman , Z. Galil, [Solving dense subset-sum problems by using analytical number theory](http://dl.acm.org/citation.cfm?id=68751&CFID=300414753&CFTOKEN=22641006), Journal of Complexity, v.5 n.3, p.271-282, Sept. 1989

**Tags:** subset-sum
> **Comments:**
> **username_1**: Why pseudo-polynomial?  
> **username_0**: 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.  
> **username_1**: I see, I thought may be |X| is  in $\Omega(n)$.  

---

## 0 answers

