back to listing index

### Finding all possible combinations of numbers to reach a given sum

[web search]
Original source (stackoverflow.com)
Tags: algorithms
Clipped on: 2016-05-28

5,258 32956

# Finding all possible combinations of numbers to reach a given sum

How would you go about testing all possible combinations of additions from a given set of numbers so they add up to a given final number?

Example:

• Set of numbers to add: {1,5,22,15,0,...}
• Desired result: 12345

P.S: Asking this problem as maths isn't my forte and wondering how this could be adapted in code.

## protected by Community♦Jan 7 at 9:42

This question is protected to prevent "thanks!", "me too!", or spam answers by new users. To answer it, you must have earned at least 10 reputation on this site (the association bonus does not count).

 4 upvote flag
Homework assignment? – dthorpe Jan 8 '11 at 4:37
 4 upvote flag
The wikipedia article (en.wikipedia.org/wiki/Subset_sum_problem) even mentions that this problem is a good introduction to the class of NP-complete problems. – user57368 Jan 8 '11 at 4:42
 1 upvote flag
@jmort253: I don't think there are any constraints other than having a set of integers which are positive and lower than the number given as a target. Any combination of numbers can be used. It isn't homework but the sort of problem that you'll be given to solve if you apply for some jobs. I can usually think up an algorithm when needed but I'm not sure how to view something like this. It needs to be decomposed somehow (recursive?). – James Poulson Jan 8 '11 at 5:14
 2 upvote flag
@James, Do you need the combinations or just the number of subset's that add upto the sum? – st0le Jan 8 '11 at 5:39
 1 upvote flag
Can we use the same element of the original set more than once? For example if the input is {1,2,3,5} and target 10, is 5 + 5 = 10 an acceptable solution? – antonis_wrx Aug 23 '15 at 0:29