# Find all maximal subsets of a set of integers whose sum does not exceed a number

Hello, I'd like to know the name of the problem (or a similar problem) that I state below:

Suppose we have a finite set of positive integers. I need to find all the subsets of integers whose sum is less than a constant C and I'd like these sets to be maximal: such that adding any other integer to that set would cause it to overgrow the constant C.

It seems to be fundamental problem and there should be a name for it!

Any ideas?

-
Sounds like the knapsack problem. – Chris Aholt Mar 4 '11 at 16:18
The 0-1 knapsack problem (en.wikipedia.org/wiki/Knapsack_problem) asks to find the maximum achievable sum in the situation you describe. – Emil Jeřábek Mar 4 '11 at 16:18
While this is essentially contained in the previous comment, the additional key-word 'subset sum problem' might also be of help, see en.wikipedia.org/wiki/Subset_sum_problem – user9072 Mar 4 '11 at 16:44
You should be able to 'efficiently' answer this problem with dynamic programming, since at every point either you have a solution or one or more elements of the set can be added to the collection. I quote "efficiently" because the number of subsets is likely to be large and so even if the algorithm is linear in the size of the output it could be quite time-consuming. A small modification to the algorithm would allow multisets rather than sets. – Charles Mar 7 '11 at 0:16
Here is a solution implemented in Python: docs.google.com/document/d/… Regards, Auden RovelleQuartz – user2759990 Sep 17 '13 at 19:07

As said, solving the Knapsack problem would mean to determine the largest sum $s\le C$ you can obtain. To ask for any specific $n$ whether there is a subset with sum $n$ would be (a form of) the Subset Sum problem.
Now, you ask for the sets and not the value of the sum, so your question is closer to the Inverse Problem associated to these problems; that is the determination of the collection of all solutions to the above problems, i.e., all sets that sum to $s$ (or $n$). (Note: Inverse Problem is an actual technical term.)
As said, this is not exactly what you asked for but quite similar; in particular, if you would solve Inverse Subset Sum for all $n \le C$ you would not get what you want as the maximality condition is omitted.