Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose I have the set of weights $W = \{w_1,w_2,\ldots,w_{50}\}$ where each $1 \le w_i \le 60$ is an integer. I am interested in determining all subsets (not just one, and not just the number of them) of $W$ with a fixed sum $s$. I realize this is obviously NP-hard, but are there some efficient ways (e.g. dynamic programming) to obtain this result for these relatively nice conditions (e.g. only 50 items, weights integer and bounded)?

share|cite|improve this question

The dynamic programming algorithm can be adapted to give all solutions. You create a table $A$. The cell $A_{k,w}$ contains enough information to enumerate all subsets of $\{w_1,\ldots,w_k\}$ summing to $w$. When $k = 0$, this is trivial. Given $A_{k-1,\cdot}$, $A_{k,w}$ points at the two cells $A_{k-1,w},A_{k-1,w-w_k}$ (if they exist). The second pointer is also annotated with $w_k$. If you look at $A_{50,W}$, you can reconstruct all subsets by considering all paths going all the way to $A_{0,0}$. This can be done using a simple recursive procedure.

share|cite|improve this answer

Yes, there is. Have a look at:

share|cite|improve this answer
However, this seems to only give the existence of such a subset -- whereas, I am interested in determining all such subsets. Do you have an idea of how I could modify it to obtain that? – Bob S. Jan 10 '13 at 21:10
You will create an array (2-D). There you can find what you are looking for ("stepping back"). There is a rich material of this problem on the internet. Just google subset sum dynamic programming. – AJed Jan 10 '13 at 22:36

Look at the coin change problem. Solutions are known which will give all results. If you have a problem with it, I can provide some code.

See for example

share|cite|improve this answer
The coin change problem that you refer to, especially the 3 variants mentioned in the link you provide, all can use the same coin multiple times. This is not the case in the question. The question is the subset sum problem, even if this too can be solved using dynamic programming. – Paresh Feb 10 '13 at 9:50
That's not the problem same. – jonaprieto Feb 26 '13 at 5:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.