Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|improve this question
add comment

3 Answers

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|improve this answer
add comment

Yes, there is. Have a look at: http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution

share|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
1  
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
add comment

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 http://www.algorithmist.com/index.php/Coin_Change for example

share|improve this answer
1  
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. –  d555 Feb 26 '13 at 5:31
add comment

Your Answer

 
discard

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.