Size K subset sum problem?

Question

I am trying to solve the following problem - I have a set of $n$ elements consisting of objects say from $O_1$ to $O_n$ ($\{O1_,O_2,O_3,........,O_n$}). Each of those elements are mapped to an integer in a specific range (for the sake of simplicity that the range is all integers less than 1000). The goal of the problem is to find the sum of the values of all the different subsets of size at least $R$. So if the set has 5 elements, then I am interested in the sum of the elements of all the subsets that have at least $R$ elements in them (if $R = 2$ , for example, then all subsets of size at least $2$). The only solution I am able to think about is to list all subsets of size at least $R$ and then sum the values of their constituent elements. It would be great if someone could provide some insight into this problem.

Answer 1

Think of how many times each element contributes to the sum. To make a subset of size $k$ that includes a particular element we need to select $k-1$ other members from the remaining $n-1$. That means each element is counted in the final sum $n-1\choose k-1$ times for the $k$ element subsets. Now we can sum over $k$ from $R$ to $n$. Each element gets added $$\sum_{k=R}^n{n-1 \choose k-1}$$ times and your final sum is just the sum of all the elements in your set times this, or $$\left(\sum_{i=1}^nO_i\right)\left(\sum_{k=R}^n{n-1 \choose k-1}\right)$$

Answer 2

Let's say each object has weight at most $W$. Here is a dynamic programming solution that runs in time $O(n^2WR)$.

Our goal will be to construct a two-dimensional array, $dp$, such that $dp[m][w] = 1$ (for $0\leq m \leq R$, $0 \leq w \leq nW$) if there exists a subset of size $m$ (or if $m=R$, subset of size at least $R$) with weight $w$.

We can do this iteratively as follows. We start with $dp[0][0] = 1$ and all other entries 0. On step $i$, we'll look at the $i$th object, $O_i$; let's say it has weight $w_i$. Then for each $w$, and each $m$, if $dp[w][m] = 1$, we can set $dp[w+w_{i}][m+1]$ to $1$ (and if $m = R$, we can set $dp[w+w_{i}][R]$ to $1$ if $dp[w][R] = 1$). This corresponds to trying to add the $i$th object to all the sets we've seen so far.

Finally, the final sums are just the values of $w$ for which $dp[w][R] = 1$. Each step above loops over the $nWR$ elements of the array, so overall this takes time $O(n^2WR)$.