<p>Even if $s$ is not constant, a dynamic programming algorithm similar to that for the knapsack problem would work.  For this to be polynomial time, we need each $w_i$ to be polynomial in $n$ (implying that $k \leq \sum w_i$ is polynomial in n).</p>

<p>The idea is that $T(j,i)$ is the number of subsets of weight $j$ and cardinality $i$.  Start with all $T(j,i) = 0$ except $T(0,0) = 1$</p>

<p>Then:</p>

<pre><code>For i = 1 to $n$
For j = 0 to $k$
For h = 1 to $s$
T(w_i + j,h+1) += T(j,h)
</code></pre>

<p>Then your answer is $\sum_{j \leq k} T(j,s)$</p>

<p>$s$, $n$, and $w_i$ (and therefore $k$) are all polynomial so all of this is polynomial.  Specifically this is at worst $O(n^2k)$ time.</p>

CC BY-SA 3.0
2012-08-07T22:55:15.810Z
Something seems wrong here in the solution. Consider w_1=1 and w_2=2, then T(2,2)=1.
h.a
CC BY-SA 3.0
2012-07-08T19:17:55.397Z
2012-07-08T22:34:28.767Z
2012-07-08T22:34:28.767Z
SamM
<p>I am interested in the following variant of the subset sum problem:</p>

<p>Given a set of positive integer weights $w_1,..., w_n$, such that each $w_i$ is polynomial in $n$, and given integers $s$ and $k$, count the number of subsets of weights of cardinality exactly $s$ such that the sum of the weights in each subset is at most $k$.</p>

<p>I expect that there is a polynomial-time dynamic programming algorithm for this problem but don't have a reference. Can anyone please point me to the relevant reference? </p>

CC BY-SA 3.0
2012-07-09T18:18:17.570Z
Yes. But let us assume that $s$ is not constant.
h.a
<cc.complexity-theory><counting-complexity>
A counting subset sum problem with fixed subset size and bounded weights
h.a
# A counting subset sum problem with fixed subset size and bounded weights

(Asked by: username_0 on 2012-07-08)

I am interested in the following variant of the subset sum problem:

Given a set of positive integer weights $w\_1,..., w\_n$, such that each $w\_i$ is polynomial in $n$, and given integers $s$ and $k$, count the number of subsets of weights of cardinality exactly $s$ such that the sum of the weights in each subset is at most $k$.

I expect that there is a polynomial-time dynamic programming algorithm for this problem but don't have a reference. Can anyone please point me to the relevant reference?

**Tags:** cc.complexity-theory, counting-complexity

> **Comments:**
> **username_0**: Yes. But let us assume that $s$ is not constant.  

---

## 1 answers

### Answer by username_1 on 2012-07-08. Score: 4 | Accepted answer

Even if $s$ is not constant, a dynamic programming algorithm similar to that for the knapsack problem would work.  For this to be polynomial time, we need each $w_i$ to be polynomial in $n$ (implying that $k \leq \sum w_i$ is polynomial in n).
The idea is that $T(j,i)$ is the number of subsets of weight $j$ and cardinality $i$.  Start with all $T(j,i) = 0$ except $T(0,0) = 1$
Then:
For i = 1 to $n$
For j = 0 to $k$
For h = 1 to $s$
T(w_i + j,h+1) += T(j,h)

Then your answer is $\sum_{j \leq k} T(j,s)$
$s$, $n$, and $w_i$ (and therefore $k$) are all polynomial so all of this is polynomial.  Specifically this is at worst $O(n^2k)$ time.

> **Comments:**
> **username_0**: Something seems wrong here in the solution. Consider w_1=1 and w_2=2, then T(2,2)=1.  

---

