# A counting subset sum problem with fixed subset size and bounded weights

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?

• Yes. But let us assume that $s$ is not constant. – h.a Jul 9 '12 at 18:18

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.

• Something seems wrong here in the solution. Consider w_1=1 and w_2=2, then T(2,2)=1. – h.a Aug 7 '12 at 22:55