Find all combinations of a list of numbers with a given sum
You could use itertools to iterate through every combination of every possible size, and filter out everything that doesn't sum to 10:
import itertools
numbers = [1, 2, 3, 7, 7, 9, 10]
target = 10
result = [seq for i in range(len(numbers), 0, -1)
for seq in itertools.combinations(numbers, i)
if sum(seq) == target]
print(result)
Result:
[(1, 2, 7), (1, 2, 7), (1, 9), (3, 7), (3, 7), (10,)]
Unfortunately this is something like O(2^N) complexity, so it isn't suitable for input lists larger than, say, 20 elements.
How to get all combination for a given sum with a given number of elements
A very simple approach is to use itertools.combinations
to generate all the possible combinations, and select those that produce the desired sum.
>>> import itertools
>>> numbers = [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9]
>>> target_sum = 1
>>> number = 3
>>> [c for c in itertools.combinations(numbers, number) if sum(c) == target_sum]
[(0.1, 0.2, 0.7), (0.1, 0.3, 0.6), (0.1, 0.4, 0.5), (0.2, 0.3, 0.5)]
If you want all the possible different orderings as distinct solutions, use itertools.permutations
instead:
>>> [c for c in itertools.permutations(numbers, number) if sum(c) == target_sum]
[(0.1, 0.2, 0.7), (0.1, 0.3, 0.6), (0.1, 0.4, 0.5), (0.1, 0.5, 0.4), (0.1, 0.6, 0.3), (0.1, 0.7, 0.2), (0.2, 0.1, 0.7), (0.2, 0.3, 0.5), (0.2, 0.5, 0.3), (0.3, 0.1, 0.6), (0.3, 0.2, 0.5), (0.3, 0.5, 0.2), (0.4, 0.1, 0.5), (0.4, 0.5, 0.1), (0.5, 0.1, 0.4), (0.5, 0.2, 0.3), (0.5, 0.3, 0.2), (0.5, 0.4, 0.1), (0.6, 0.1, 0.3), (0.7, 0.1, 0.2)]
If you want to be able to use each element more than once, use itertools.combinations_with_replacement
:
>>> [c for c in itertools.combinations_with_replacement(numbers, number) if sum(c) == target_sum]
[(0.1, 0.1, 0.8), (0.1, 0.2, 0.7), (0.1, 0.3, 0.6), (0.1, 0.4, 0.5), (0.2, 0.2, 0.6), (0.2, 0.3, 0.5), (0.2, 0.4, 0.4), (0.3, 0.3, 0.4)]
If you want to use elements multiple times and get all the possible orderings, use itertools.product
:
>>> [c for c in itertools.product(numbers, repeat=number) if sum(c) == target_sum]
[(0.1, 0.1, 0.8), (0.1, 0.2, 0.7), (0.1, 0.3, 0.6), (0.1, 0.4, 0.5), (0.1, 0.5, 0.4), (0.1, 0.6, 0.3), (0.1, 0.7, 0.2), (0.1, 0.8, 0.1), (0.2, 0.1, 0.7), (0.2, 0.2, 0.6), (0.2, 0.3, 0.5), (0.2, 0.4, 0.4), (0.2, 0.5, 0.3), (0.2, 0.6, 0.2), (0.3, 0.1, 0.6), (0.3, 0.2, 0.5), (0.3, 0.3, 0.4), (0.3, 0.4, 0.3), (0.3, 0.5, 0.2), (0.4, 0.1, 0.5), (0.4, 0.2, 0.4), (0.4, 0.3, 0.3), (0.4, 0.4, 0.2), (0.4, 0.5, 0.1), (0.5, 0.1, 0.4), (0.5, 0.2, 0.3), (0.5, 0.3, 0.2), (0.5, 0.4, 0.1), (0.6, 0.1, 0.3), (0.6, 0.2, 0.2), (0.7, 0.1, 0.2), (0.8, 0.1, 0.1)]
Finding all possible combinations of numbers to reach a given sum
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 Stanford'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.
Given a list of numbers, how do you create all the combinations of sums and return a list of those sum
Using itertools.permutations
:
>>> import itertools
>>> nums = [1, 2, 3]
>>> [sum(p) for n in range(1, len(nums)+1) for p in itertools.permutations(nums, n)]
[1, 2, 3, 3, 4, 3, 5, 4, 5, 6, 6, 6, 6, 6, 6]
If you want to see exactly what permutations
is doing rather than just seeing the final sums, you can do fun things with map
and join
:
>>> [f"{'+'.join(map(str, p))}={sum(p)}" for n in range(1, len(nums)+1) for p in itertools.permutations(nums, n)]
['1=1', '2=2', '3=3', '1+2=3', '1+3=4', '2+1=3', '2+3=5', '3+1=4', '3+2=5', '1+2+3=6', '1+3+2=6', '2+1+3=6', '2+3+1=6', '3+1+2=6', '3+2+1=6']
Generating all combinations of list of numbers where the sum of the combination is = N
A simple k-combination of a finite set S is a subset of k distinct elements of S. Specifying a subset does not arrange them in a particular order.
You can use the CombinatoricsLib. CombinatoricsLib is a java library for generating combinatorial objects. https://code.google.com/p/combinatoricslib/
Using this:
public static void main(String[] args) {
// Create the initial vector
ICombinatoricsVector<Integer> initialVector = Factory.createVector(
new Integer[] {1, 5, 4, 3, 6, 9, 7, 4, 3, 8, 2, 1, 6, 3, 7} );
int subsetMaxSize = 5;
int upperLimit = 10;
int lowerLimit = 8;
for(int i = 1; i <= subsetMaxSize; i++)
{
Generator<Integer> gen = Factory.createSimpleCombinationGenerator(initialVector, i);
for (ICombinatoricsVector<Integer> combination : gen)
{
int sum = vectorSum(combination);
if(validateSum(sum, lowerLimit, upperLimit))
printVector(combination);
}
}
}
public static boolean validateSum(Integer value, Integer lowerLimit, Integer upperLimit)
{
if(value <= upperLimit && value > lowerLimit)
return true;
return false;
}
public static Integer vectorSum(ICombinatoricsVector<Integer> vect)
{
Integer sum = 0;
for(int i = 0; i < vect.getSize(); i++)
sum += vect.getValue(i);
return sum;
}
public static void printVector(ICombinatoricsVector<Integer> vect)
{
String output = "";
for(int i = 0; i < vect.getSize(); i++)
output += vect.getValue(i) + ", ";
System.out.println(output);
}
will return the output
9,
1, 9,
1, 8,
5, 4,
5, 4,
4, 6,
4, 6,
3, 6,
3, 7,
3, 6,
3, 7,
6, 4,
6, 3,
6, 3,
9, 1,
7, 3,
7, 2,
7, 3,
4, 6,
3, 6,
3, 7,
8, 2,
8, 1,
2, 7,
6, 3,
3, 7,
1, 5, 4,
1, 5, 3,
1, 5, 4,
1, 5, 3,
1, 5, 3,
1, 4, 4,
1, 3, 6,
1, 3, 6,
1, 6, 3,
1, 6, 2,
1, 6, 3,
1, 7, 2,
1, 7, 1,
1, 3, 6,
1, 8, 1,
1, 2, 6,
1, 2, 7,
1, 1, 7,
1, 6, 3,
5, 4, 1,
5, 3, 2,
5, 3, 1,
5, 4, 1,
5, 3, 2,
5, 3, 1,
5, 2, 3,
5, 1, 3,
4, 3, 3,
4, 3, 2,
4, 3, 3,
4, 4, 2,
4, 4, 1,
4, 3, 2,
4, 3, 3,
4, 2, 3,
3, 6, 1,
3, 4, 3,
3, 4, 2,
3, 4, 3,
3, 3, 3,
3, 1, 6,
6, 3, 1,
6, 2, 1,
6, 1, 3,
7, 2, 1,
4, 3, 2,
4, 3, 3,
4, 2, 3,
3, 1, 6,
2, 1, 6,
2, 1, 7,
1, 6, 3,
1, 5, 3, 1,
1, 5, 3, 1,
1, 5, 2, 1,
1, 5, 1, 3,
1, 4, 3, 2,
1, 4, 3, 1,
1, 4, 4, 1,
1, 4, 3, 2,
1, 4, 3, 1,
1, 4, 2, 3,
1, 4, 1, 3,
1, 3, 4, 2,
1, 3, 4, 1,
1, 3, 3, 2,
1, 3, 3, 3,
1, 3, 2, 3,
1, 6, 2, 1,
1, 4, 3, 2,
1, 4, 3, 1,
1, 4, 2, 3,
1, 4, 1, 3,
1, 3, 2, 3,
1, 2, 1, 6,
4, 3, 2, 1,
4, 3, 2, 1,
4, 2, 1, 3,
3, 4, 2, 1,
3, 3, 2, 1,
3, 3, 1, 3,
3, 2, 1, 3,
4, 3, 2, 1,
4, 2, 1, 3,
3, 2, 1, 3,
1, 3, 3, 2, 1,
1, 3, 2, 1, 3,
1, 3, 2, 1, 3,
Finding all possible combinations of numbers of an array to reach a given sum
Took me while to code this. So it's basically brute force. I recursively (backtracking) generate all possible expression with the operators given and then evaluate them. Note these are just infix expression(s).
Now this is a very slow solution. There are several optimization one can do here.
vector<string> allCombinations(vector<int> &arr, int k)
{
int n = (int)arr.size();
string operators = "+-*";
vector<string> ans;
// To check precedence of operators
auto prec = [&](char op) -> int
{
if (op == '*' or op == '/') return 2;
if (op == '+' or op == '-') return 1;
return -1;
};
// For infix evaluation (kindof a helper function)
auto compute = [&](int v1, char op, int v2) -> int
{
if (op == '+') return v1 + v2;
if (op == '-') return v1 - v2;
if (op == '*') return v1 * v2;
if (op == '/') return v1 / v2;
assert(false);
return INT_MAX;
};
// Main infix evaluation function
auto evaluate = [&](string s) -> int
{
int len = (int)s.size();
// vector is being used as a STACK
vector<int> val;
vector<char> ops;
for (int i = 0; i < len; i++)
{
char curr = s[i];
if (curr == ' ') continue;
if (isdigit(curr))
{
int v = 0;
while (i < len and isdigit(s[i])) v = 10 * v + (s[i++] - '0');
val.push_back(v);
i--;
}
else
{
while (!ops.empty() and prec(curr) <= prec(ops.back()))
{
int v1 = val.back();
val.pop_back();
int v2 = val.back();
val.pop_back();
char op = ops.back();
ops.pop_back();
val.push_back(compute(v2, op, v1));
}
ops.push_back(curr);
}
}
while (!ops.empty())
{
int v1 = val.back();
val.pop_back();
int v2 = val.back();
val.pop_back();
char op = ops.back();
ops.pop_back();
val.push_back(compute(v2, op, v1));
}
return val.back();
};
// Generates all expression possible
function<void(int, string&)> generate = [&](int i, string &s) -> void
{
s += to_string(arr[i]);
if (i == n - 1)
{
if (evaluate(s) == k) ans.push_back(s);
// Backtrack
s.pop_back();
return;
}
for (char &ops : operators)
{
s.push_back(ops);
generate(i + 1, s);
// Backtrack
s.pop_back();
}
// Backtrack
s.pop_back();
};
string s;
// Try all combinations
sort(arr.begin(), arr.end());
do
{
generate(0, s);
} while (next_permutation(arr.begin(), arr.end()));
return ans;
}
Related Topics
Asynchronous Method Call in Python
How to Serve Multiple Clients Using Just Flask App.Run() as Standalone
Convert Column to Date Format (Pandas Dataframe)
Permanent Fix for Opencv Videocapture
Building Python with Ssl Support in Non-Standard Location
What Does % Do to Strings in Python
Regex to Extract Urls from Href Attribute in HTML with Python
Using Beautifulsoup to Extract Text Without Tags
How to Plot and Annotate a Grouped Bar Chart
Purpose of Calling Function Without Brackets Python
(Z3Py) Checking All Solutions for Equation
Difference in Boto3 Between Resource, Client, and Session
Why Does Python Assignment Not Return a Value
Is It Ok to Use Dashes in Python Files When Trying to Import Them