Suppose I have a set $\mathcal{S}$ of $N$ positive integers, and I want to compute the number of subsets of $\mathcal{S}$ whose elements sum to at most $M$.
Clearly this problem will require exponential time in the worst-case, by reduction from ordinary subset-sum.
If $M$ is small, standard dynamic programming approaches can be applied; let's assume $M$ is very large but $N$ is small (say, 40).
Then I propose the following algorithm:
- sort the elements of $\mathcal{S}$ in descending order;
- if the sum of the remaining elements in $\mathcal{S}$ is at most $M$, return $2^{|\mathcal{S}|}$ (note this step can be made efficient by precomputing suffix sums of $\mathcal{S}$);
- otherwise let $k$ be the largest element of $\mathcal{S}$. Recurse on the two cases (i) where I add $k$ to my subset, and decrease $M$ by $k$; and (ii) where I discard $k$ from $\mathcal{S}$ without adding it to my subset; and add the two results.
I'm having trouble analysing the worst-case behavior of this algorithm. My intution tells me it's something like $O(N 2^{N/2})$ since it's hard to force the algorithm to explore a full decision tree of size $2^N$: either you choose a lot of large elements early, and then have no decision to make later, or you eschew the large elements and then optimize away the cases where you have a lot of small elements left.
- What is the worst-case behavior of the above algorithm?
- Is there an asymptotically more efficient solution to the original problem?