list all the permutation to sum up some numbers to a dest number

Question

Possible Duplicate:
Algorithm to find which number in a list sum up to a certain number

question:

there is a list: [1,2,3,4,6,8,10,12], i want to use these numbers to sum up to a new number 16.

rules:

1) don't need to use all of the numbers, 6 + 10 will be ok.

2) a number can use multi times, 12+2+1+1 will be ok.

3) order matters, 12 + 6 and 6 + 12 are two different combinations.

i have see algorithm to sum up a list of numbers for all combinations, but this is not the same.

don't know much about algorithm, if this fit certain algorithm, please let me know, or some python code / pseudo-code will be much appreciated.

What have you tried so far? Also, see [Find combinations of numbers that sum to some desired number](http://stackoverflow.com/q/3363250/62576), [Algorithm to find which number in a list sum up to a certain number](http://stackoverflow.com/q/3420937/62576), and [Finding all possible combinations of numbers to reach a given sum](http://stackoverflow.com/q/4632322/62576), among others. — Ken White, Dec 05 '12 at 03:25
A number can be used multiple times _and_ order matters? Oh boy, look at all the combinations of `2+1+1+1+1+1+1+1+1+1+1+1+1+1+1` you'll have to have. — TheZ, Dec 05 '12 at 03:27
@KenWhite thanks for your link, i have read some, maybe i need to dig deeper — limboy, Dec 05 '12 at 03:34
Since order matters perhaps you should refer to your "combinations" as permutations. — Akavall, Dec 05 '12 at 03:42

score 4 · Accepted Answer · edited May 23 '17 at 10:34

First - note that even finding if there is any subset that sums to the desired number is NP-Complete and is known as the subset sum problem, so there is no known polynomial solution for it.

Now, regarding the specific issue, here are some options:

First there is of course the obvious "generate all subsets and check the sum" way. Note that if your elements are all non-negative, you can use branch and bound and terminate a large portion of the possibilities before you actually develop them (If you found a subset X with sum(X) == s, and you are looking for the number n < s - you can be sure any set containing X will NOT find the solution). Something along the lines of:

findSubsets(list,sol,n):
  if (list.empty() and n == 0): #found a feasible subset!
     print sol 
     return
  else if (n < 0): #bounding non feasible solutions
     return 
  else if (list.empty()): #a solution that sums to a smaller number then n
     return
  e <- list.removeAndReturnFirst()
  sol <- sol.add(e)
  findSubsets(list,sol,n-e)
  sol <- sol.removeLast()
  findSubsets(list,sol,n)
  list.addFirst(e) #cleanup, return the list to original state

Invoke with findSubsets(list,[],n) where list is your list of items, n is the desired number and [] is an empty list.

Note that it can be easily parallelized if needed, there is no real syncrhonization needed between two subsets explored.

Another alternative if the list contains only integers is using Dynamic Programming for solving the subset sum problem. Once you have the matrix you can re-create all the elements from the table by going back in the table. This similar question discusses how to get a list from the knapsack DP solution. The principles of the two problems are pretty much the same.

list all the permutation to sum up some numbers to a dest number

1 Answers1