Finding all possible combinations of numbers to reach a given sum
[web search]
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:
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:42This 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). 



This problem can be solved with a recursive combinations of all possible sums filtering out those that reach the target. Here is the algorithm in Python:
This type of algorithms are very well explained in the following Standford's Abstract Programming lecture  this video is very recommendable to understand how recursion works to generate permutations of solutions. Edit The above as a generator function, making it a bit more useful. Requires Python 3.3+ because of
Here is the Java version of the same algorithm:
It is exactly the same heuristic. My Java is a bit rusty but I think is easy to understand. C# conversion of Java solution: (by @JeremyThompson)
Ruby solution: (by @emaillenin)
Edit: complexity discussion As others mention this is an NP problem. It can be solved in exponential time O(2^n), for instance for n=10 there will be 1024 possible solutions. If the targets you are trying to reach are in a low range then this algorithm works. So for instance:
On the other hand If



In Haskell:
And J:
As you may notice, both take the same approach and divide the problem into two parts: generate each member of the power set, and check each member's sum to the target. There are other solutions but this is the most straightforward. Do you need help with either one, or finding a different approach?



The solution of this problem has been given one million times on the Internet. The problem is called The coin changing problem. One can find solutions at http://rosettacode.org/wiki/Count_the_coins and mathematical model of it at http://jaqm.ro/issues/volume5,issue2/pdfs/patterson_harmel.pdf (or Google coin change problem). By the way, the Scala solution by Tsagadai, is interesting. This example produces either 1 or 0. As a side effects, it lists on the console all possible solutions. It displays the solution, but fails making it usable in any way. To be as useful as possible, the code should return a Here is an example. It is very inefficient, but it is easy to understand.
When run, it displays:
The sumCombinations() function may be used by itself, and the result may be further analyzed to display the "best" solution (the shortest list), or the number of solutions (the number of lists). Note that even like this, the requirements may not be fully satisfied. It might happen that the order of each list be significant. In such a case, each list would have to be duplicated as many time as there are combination of its elements. Or we might be interested only by the combination that are different. For example, we might consider that List(5, 10) should give two combinations: List(5, 10) and List(10, 5). For List(5, 5, 5) it could give three combinations or one only, depending on the requirements. For integers, the three permutations are equivalent, but if we are dealing with coins, like in the "coin changing problem", they are not. Also not stated in the requirements is the question of whether each number (or coin) may be used only once or many times. We could (and we should!) generalized the problem to a list of lists of occurrences of each number. This translates in real life into "what are the possible ways to make an certain amount of money with a set of coins (and not a set of coin values). The original problem is just a particular case of this one, where we have as many occurrences of each coin as needed to make the total amount with each single coin value.



C# version of @msalvadores code answer


A Javascript version:


C++ version of the same algorithm


i have converted above logic from python to php..



I thought I'd use an answer from this question but I couldn't, so here is my answer. It is using a modified version of an answer in Structure and Interpretation of Computer Programs. I think this is a better recursive solution and should please the purists more. My answer is in Scala (and apologies if my Scala sucks, I've just started learning it). The findSumCombinations craziness is to sort and unique the original list for the recursion to prevent dupes.
To use it:


This is similar to a coin change problem


To find the combinations using excel  (its fairly easy). (You computer must not be too slow)
hope this helps.


Another python solution would be to use the itertools.combinations module as follows:
Output: [(8, 7), (5, 10), (3, 8, 4), (3, 5, 7)]


Very efficient algorithm using tables i wrote in c++ couple a years ago. If you set PRINT 1 it will print all combinations(but it wont be use the efficient method). Its so efficient that it calculate more than 10^14 combinations in less than 10ms.


@KeithBeller's answer with slightly changed variable names and some comments.


I ported the C# sample to Objectivec and didn't see it in the responses:



Excel VBA version below. I needed to implement this in VBA (not my preference, don't judge me!), and used the answers on this page for the approach. I'm uploading in case others also need a VBA version.
Output (written to the Immediate window) should be:


This can be used to print all the answers as well
Time Complexity is exponential. Order of 2^n


Your Answer
asked 
5 years ago 
viewed 
122177 times 
active 
Visit Chat
Linked
Related
Technology  Life / Arts  Culture / Recreation  Science  Other  
