I have a list of numbers, finite, about 50 and I want to know which permutations with subsets of that set sum up to a given number. I found a formula for the number of ways but I don't know how to find the actual numbers. Can you help me?
How to find the numbers that sum up to a given number?
-
0It's similar to the subset-sum problem and might be transformed to that. As far as I can tell you have understood the question correctly. I think it is a nice question because it is easy to understand. – 2012-10-04
1 Answers
I assume you mean you want to find the subsets of your list whose sum is a given number $S$. You can do it with dynamic programming. Suppose your numbers $x_1, \ldots, x_n$ are positive integers and the target sum is $s$. If $A_{k,m}$ for $1 \le k \le n$, $0 \le m \le s$, is the number of subsets of $\{x_1, \ldots, x_k\}$ whose sum is $m$, we have $A_{1,0} = A_{1,x_1} = 1$, $A_{1,m} = 0$ otherwise, and for $k \ge 2$, $A_{k,m} = A_{k-1,m} + A_{k-1,m-x_k}$ if $m \ge x_k$, $A_{k-1,m}$ if $m < x_k$.
Now if $A_{k,m} > 0$ we enumerate the subsets of $\{x_1,\ldots,x_k\}$ with sum $m$ recursively as follows: if $A_{k-1,m} > 0$, first enumerate the subsets of $\{x_1,\ldots,x_{k-1}\}$ with sum $m$; then if $m \ge x_k$ and $A_{k-1,m-x_k} > 0$ enumerate the subsets of $\{x_1,\ldots,x_{k-1}\}$ with sum $m-x_k$ and adjoin $x_k$ to each.
-
0Thank you for the answer. As far as I can tell you've understood the question correctly. – 2012-10-04