## 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

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:

def subset_sum(numbers, target, partial=[]): s = sum(partial) # check if the partial sum is equals to target if s == target: print "sum(%s)=%s" % (partial, target) if s >= target: return # if we reach the number why bother to continue for i in range(len(numbers)): n = numbers[i] remaining = numbers[i+1:] subset_sum(remaining, target, partial + [n]) if __name__ == "__main__": subset_sum([3,9,8,4,5,7,10],15) #Outputs: #sum([3, 8, 4])=15 #sum([3, 5, 7])=15 #sum([8, 7])=15 #sum([5, 10])=15

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 `yield from`

.

def subset_sum(numbers, target, partial=[], partial_sum=0): if partial_sum == target: yield partial if partial_sum >= target: return for i, n in enumerate(numbers): remaining = numbers[i + 1:] yield from subset_sum(remaining, target, partial + [n], partial_sum + n)

Here is the Java version of the same algorithm:

package tmp; import java.util.ArrayList; import java.util.Arrays; class SumSet { static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) { int s = 0; for (int x: partial) s += x; if (s == target) System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target); if (s >= target) return; for(int i=0;i<numbers.size();i++) { ArrayList<Integer> remaining = new ArrayList<Integer>(); int n = numbers.get(i); for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j)); ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial); partial_rec.add(n); sum_up_recursive(remaining,target,partial_rec); } } static void sum_up(ArrayList<Integer> numbers, int target) { sum_up_recursive(numbers,target,new ArrayList<Integer>()); } public static void main(String args[]) { Integer[] numbers = {3,9,8,4,5,7,10}; int target = 15; sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target); } }

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)*

public static void Main(string[] args) { List<int> numbers = new List<int>() { 3, 9, 8, 4, 5, 7, 10 }; int target = 15; sum_up(numbers, target); } private static void sum_up(List<int> numbers, int target) { sum_up_recursive(numbers, target, new List<int>()); } private static void sum_up_recursive(List<int> numbers, int target, List<int> partial) { int s = 0; foreach (int x in partial) s += x; if (s == target) Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target); if (s >= target) return; for (int i = 0; i < numbers.Count; i++) { List<int> remaining = new List<int>(); int n = numbers[i]; for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]); List<int> partial_rec = new List<int>(partial); partial_rec.Add(n); sum_up_recursive(remaining, target, partial_rec); } }

**Ruby solution:** *(by @emaillenin)*

def subset_sum(numbers, target, partial=[]) s = partial.inject 0, :+ # check if the partial sum is equals to target puts "sum(#{partial})=#{target}" if s == target return if s >= target # if we reach the number why bother to continue (0..(numbers.length - 1)).each do |i| n = numbers[i] remaining = numbers.drop(i+1) subset_sum(remaining, target, partial + [n]) end end subset_sum([3,9,8,4,5,7,10],15)

**Edit: complexity discussion**

As others mention this is an NP-hard 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:

`subset_sum([1,2,3,4,5,6,7,8,9,10],100000)`

generates 1024 branches because the target never gets to filter out possible solutions.

On the other hand `subset_sum([1,2,3,4,5,6,7,8,9,10],10)`

generates only 175 branches, because the target to reach `10`

gets to filter out many combinations.

If `N`

and `Target`

are big numbers one should move into an approximate version of the solution.

**Find all combinations that add upto given number,** Minimum possible sum of array elements after performing the given operation Given a positive number, find out all combinations of positive numbers that Find all combinations that equal a given sum with an amazing feature Maybe all of the above methods are somewhat difficult for you, here, I will introduce a powerful-tool, Kutools for Excel , with its Make Up A Number feature, you can quickly get all combinations that equal to a given sum.

The solution of this problem has been given a 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/volume-5,issue-2/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 effect, 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 `List[List[Int]]`

in order to allow getting the number of solution (length of the list of lists), the "best" solution (the shortest list), or all the possible solutions.

Here is an example. It is very inefficient, but it is easy to understand.

object Sum extends App { def sumCombinations(total: Int, numbers: List[Int]): List[List[Int]] = { def add(x: (Int, List[List[Int]]), y: (Int, List[List[Int]])): (Int, List[List[Int]]) = { (x._1 + y._1, x._2 ::: y._2) } def sumCombinations(resultAcc: List[List[Int]], sumAcc: List[Int], total: Int, numbers: List[Int]): (Int, List[List[Int]]) = { if (numbers.isEmpty || total < 0) { (0, resultAcc) } else if (total == 0) { (1, sumAcc :: resultAcc) } else { add(sumCombinations(resultAcc, sumAcc, total, numbers.tail), sumCombinations(resultAcc, numbers.head :: sumAcc, total - numbers.head, numbers)) } } sumCombinations(Nil, Nil, total, numbers.sortWith(_ > _))._2 } println(sumCombinations(15, List(1, 2, 5, 10)) mkString "\n") }

When run, it displays:

List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1) List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2) List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2) List(1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2) List(1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2) List(1, 1, 1, 1, 1, 2, 2, 2, 2, 2) List(1, 1, 1, 2, 2, 2, 2, 2, 2) List(1, 2, 2, 2, 2, 2, 2, 2) List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5) List(1, 1, 1, 1, 1, 1, 1, 1, 2, 5) List(1, 1, 1, 1, 1, 1, 2, 2, 5) List(1, 1, 1, 1, 2, 2, 2, 5) List(1, 1, 2, 2, 2, 2, 5) List(2, 2, 2, 2, 2, 5) List(1, 1, 1, 1, 1, 5, 5) List(1, 1, 1, 2, 5, 5) List(1, 2, 2, 5, 5) List(5, 5, 5) List(1, 1, 1, 1, 1, 10) List(1, 1, 1, 2, 10) List(1, 2, 2, 10) List(5, 10)

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 in the solution 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 in the combinations 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!) generalize 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.

**Combinational Sum,** Count total ways to reach destination from source in an undirected Graph · Number of pairs such Given an array of positive integers arr[] and a sum x, find all unique If there is no combination possible the print "Empty" (without quotes). Since the problem is to get all the possible results, not the best or the number of Finding all numbers that reach a given sum. and you append B onto A line by line in every possible way. know every combination I could use to reach a certain

In Haskell:

filter ((==) 12345 . sum) $ subsequences [1,5,22,15,0,..]

And J:

(]#~12345=+/@>)(]<@#~[:#:@i.2^#)1 5 22 15 0 ...

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?

**Print all combination of numbers from 1 to n having sum n,** 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:. 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

A Javascript version:

function subsetSum(numbers, target, partial) { var s, n, remaining; partial = partial || []; // sum partial s = partial.reduce(function (a, b) { return a + b; }, 0); // check if the partial sum is equals to target if (s === target) { console.log("%s=%s", partial.join("+"), target) } if (s >= target) { return; // if we reach the number why bother to continue } for (var i = 0; i < numbers.length; i++) { n = numbers[i]; remaining = numbers.slice(i + 1); subsetSum(remaining, target, partial.concat([n])); } } subsetSum([3,9,8,4,5,7,10],15); // output: // 3+8+4=15 // 3+5+7=15 // 8+7=15 // 5+10=15

**Find all possible combinations of numbers to print given sum ,** Given a positive integer n, print all combination of numbers from 1 to n having sum n. For example, For n = 5, below combinations are possible {5}, {1, 4}, {2, 3}, Combination Sum. Medium. Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may be chosen from candidates unlimited number of times.

C# version of @msalvadores code answer

void Main() { int[] numbers = {3,9,8,4,5,7,10}; int target = 15; sum_up(new List<int>(numbers.ToList()),target); } static void sum_up_recursive(List<int> numbers, int target, List<int> part) { int s = 0; foreach (int x in part) { s += x; } if (s == target) { Console.WriteLine("sum(" + string.Join(",", part.Select(n => n.ToString()).ToArray()) + ")=" + target); } if (s >= target) { return; } for (int i = 0;i < numbers.Count;i++) { var remaining = new List<int>(); int n = numbers[i]; for (int j = i + 1; j < numbers.Count;j++) { remaining.Add(numbers[j]); } var part_rec = new List<int>(part); part_rec.Add(n); sum_up_recursive(remaining,target,part_rec); } } static void sum_up(List<int> numbers, int target) { sum_up_recursive(numbers,target,new List<int>()); }

**Combination Sum,** The following program will print all possible combinations of additions from a given set of numbers so that they sum up to a given target number Python program to find all possible pairs with given sum. Given a list of integers and an integer variable K, write a Python program to find all pairs in the list with given sum K. Examples: This is a naive approach to the above problem. First, we take an empty list ‘res’ and start a loop and traverse each element of the given list of integers.

**Number of possible combinations of x numbers that sum to y ,** Any ideas about writing fast code finding all possible combinations of numbers to reach a given sum (target) in a matrix??? example: Target 12 Given a positive number, find out all combinations of positive numbers that adds upto that number. The program should print only combinations, not permutations. For example, for input 3, either 1, 2 or 2, 1 should be printed.

**Algorithm,** Given a set of candidate numbers ( candidates ) (without duplicates) and a target number ( target ), find all unique combinations in candidates where the Efficient algorithm to find a combination, which summation is equal to a known number, in a set of number Algorithm to find which numbers from a list of size n sum to another number Backtracking – Subset sum with C# Efficient way to generate combinations ordered by increasing sum of indexes Good luck, OI

This problem is equivalent to finding the number of integer solutions to Since every permutation of stars and "+" signs represents a solution the total number of solutions is given by the possible permutations of this 14 symbols, that is 14!10!4! Finding the total number of combinations (using permutations and factorials) - Duration: 9:39. aaron weis 8,704 views