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.
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)]
Find All Combinations of Numbers That Uniquely Sum to a Set of Numbers
You mean something like:
In []:
import itertools as it
source = [1, 2, 3, 4, 5]
targets = [3, 8]
p = [[a for n in range(1, len(source)) for a in it.combinations(source, n) if sum(a) == t] for t in targets]
[dict(zip(targets, a)) for a in it.product(*p) if len(sum(a, tuple())) == len(set(sum(a, tuple())))]
Out[]:
[{3: (3,), 8: (1, 2, 5)}, {3: (1, 2), 8: (3, 5)}]
Find all combinations of numbers that sum to a target
my_matrix <- matrix(nrow = 1000, ncol = 4)
i <- 1
nn <- 1000
while(i <= 1000){
x <- sample(x = 4:nn, size = 3)
y = nn - sum(x)
if(y >= 4){
my_matrix[i, ] <- c(x, y)
i <- i + 1
}
}
Per Gavin's suggestion, redone with a preallocated matrix. Now this runs in .158 seconds, twice as fast, and probably scales better.
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;
}
Calculate the sum of dices based on target accurately
Update
In order to find the maximum possible score of the list, we maximize the number of non-overlapping combinations that we can construct from it.
For we need to take the following steps:
Find all the possible combinations which produce the
targetsum. We can not reject any combinations on the fly, because we can't know in advance which of them can be used in the optimal solution. For instance, iftargetis6and a list of number is[3,3,2,2,1,1], there will be the following combinations:[3,3],[2,2,1,1]and[3,2,1]appear two times. If we pick[3,3], which is the shortest combination, we will not be able to construct any combinations and resulting score will be wrong (6). Instead, we need to choose two combinations[3,2,1]which well give the result12. That proves that we can't rely on the combination size, we need to explore all the combinations and then choose the optimal set of combinations.Generate all possible groups of combinations that fit to the given list of numbers and find a group having the maximum number of combinations in it.
In the code below both steps are implemented recursively.
A link to Online Demo
Expalanation:
The enty point, this method that kicks in the process.
public static int sumRecursively(List<Integer> numbers, int target) {
Deque<List<Integer>> combinations = new ArrayDeque<>();
generateCombinations(numbers, combinations, new ArrayList<>(), target);
return processCombinations(combinations, numbers, target);
}
Step 1. Generating all the combinations.
Recursive method responsible for generating the set of combinations (implemented as void to avoid wrapping a combination with an additional collection and then throwing this wrapper away):
private static void generateCombinations(List<Integer> numbers,
Queue<List<Integer>> combinations,
List<Integer> combination,
int currentSum) {
if (currentSum == 0) { // base case - a combination has been found
combinations.add(combination);
return;
}
// recursive case
for (Integer next : numbers) { // loop is need only to discard the elements that exceed the currentSum - pay attention to the condition below and break clause at the end of the loop (we will bread out of the loop after the first encountered element that fits to the current sum)
if (next > currentSum) continue;
List<Integer> newNumbers = new ArrayList<>(numbers);
newNumbers.remove(next);
// there two opportunities for each number: use it, or ignore it
// add next number
List<Integer> newCombination = new ArrayList<>(combination);
newCombination.add(next);
getCombinations(newNumbers, combinations, newCombination, currentSum - next);
// ignore next number
getCombinations(newNumbers, combinations, new ArrayList<>(combination), currentSum);
break;
}
}
Step 2. Generating the groups of combinations.
Method below is responsible choosing the group that fits to the given list (i.e. we can construct all the combinations in the group from list elements) and has the maximum number of combinations in it.
All the functionality related to the procissing the the group of combinations (which represents a List<List<Integer>>) is incapsulated in a class CombinationGroup to make the code cleaner.
public static int processCombinations(Deque<List<Integer>> combinations,
List<Integer> numbers,
int target) {
List<CombinationGroup> combinationGroups = new ArrayList<>();
generateGroups(combinationGroups, combinations, new CombinationGroup(numbers.size()));
return combinationGroups.stream()
.filter(group -> group.canConstruct(numbers))
.mapToInt(group -> group.getCombCount() * target)
.max()
.orElse(0);
}
The following method is responsible for creating the all possible groups of previosly descovered combinations. There's also a small optimization: total number of elements in each group should not exceed the number of elements in the source list:
public static void generateGroups(List<CombinationGroup> groups,
Deque<List<Integer>> combinations,
CombinationGroup group) {
if (combinations.isEmpty()) {
groups.add(group);
return;
}
Deque<List<Integer>> combinationsCopy = new ArrayDeque<>(combinations);
List<Integer> comb = null;
while (!combinationsCopy.isEmpty() && (comb == null || !group.canAdd(comb))) {
comb = combinationsCopy.removeLast();
}
// adding the combination
if (comb != null) {
CombinationGroup groupWithNewComb = group.copy();
groupWithNewComb.addCombination(comb);
generateGroups(groups, combinationsCopy, groupWithNewComb);
}
// ignoring the combination
generateGroups(groups, combinationsCopy, group);
}
Class CombinationGroup used in the methods above:
public class CombinationGroup {
private List<List<Integer>> combinations = new ArrayList<>();
private int combCount; // number of combinations
private int size; // total number of elements in the list of combinations
private int sizeLimit;
public CombinationGroup(int sizeLimit) {
this.sizeLimit = sizeLimit;
}
public boolean canAdd(List<Integer> combination) {
return size + combination.size() <= sizeLimit;
}
public boolean addCombination(List<Integer> combination) {
if (!canAdd(combination)) return false;
combinations.add(combination);
size += combination.size();
combCount++;
return true;
}
public CombinationGroup copy() {
CombinationGroup copy = new CombinationGroup(this.sizeLimit);
for (List<Integer> comb : combinations) {
copy.addCombination(comb);
}
return copy;
}
public boolean canConstruct(List<Integer> numbers) {
if (numbers.size() < size) return false;
Map<Integer, Long> frequencyByValueNumb = getFrequencies(numbers.stream());
Map<Integer, Long> frequencyByValueComb = getFrequencies();
return frequencyByValueNumb.keySet().stream() // each element that prent this CombinationGroup appears in the given list of numbers appears at least the same number of times - that means we construct all these combinations from the given list
.allMatch(key -> frequencyByValueNumb.get(key) >= frequencyByValueComb.getOrDefault(key, 0L));
}
public Map<Integer, Long> getFrequencies() {
return getFrequencies(combinations.stream().flatMap(List::stream));
}
public Map<Integer, Long> getFrequencies(Stream<Integer> stream) {
return stream.collect(Collectors.groupingBy(
Function.identity(),
Collectors.counting()
));
}
public int getCombCount() {
return combCount;
}
@Override
public String toString() {
return "CombinationGroup{" +
"combinations=" + combinations +
'}';
}
}
main()
public static void main(String[] args) {
System.out.println(sumRecursively(List.of(1, 3, 4, 5, 6, 6), 12));
System.out.println(sumRecursively(List.of(1, 3, 3, 6, 5), 12));
System.out.println(sumRecursively(List.of(1, 2, 1, 4, 5, 6), 6));
}
Output:
24
12
18
Simplified algorithm
(doesn't maximizes the number of combinations)
In order to ensure that all the elements in each combination are unique, we to track indices that have been already used. I.e. each time we find a combination which sums up to the target number, we should prohibit the usage of elements that have been used in this combination, but not earlier (because there can be many combinations which are not able to produce the target, and therefore any element should eligible to be used until we didn't construct a complete combination that gives the target using this element).
To track the elements that are taken, we need an object that would be visible in every recursive branch. And we are already passing a list of numbers while making every recursive call, what if we would modify it each time we found a combination that produces the target number by removing the elements that have been use in this combination? If we took this road after the first combination, thing would become complicated because we will not be able to rely on the indices (because they can change in an unpredictable way) while constructing a single combination - it's crucial to ensure that each element that belongs to a particular combination is used only once withing a combination. Since values of elements might be identical, we should use the iteration order to construct each combination properly, but each removal of elements would create a mess. So, is there a better way?
We can maintain an array of boolean values, each element is this array would indicate whether a number at a particular index already belongs to a combination that gives the target or not.
Instead of clattering the recursive method with the code that manipulates with this boolean array, I've encapsulated it within a class with simple and self-explanatory methods, and sumRecursively() makes use of an instance of this class.
public class CombinationTracker {
private boolean[] isUsed;
public CombinationTracker(int size) {
this.isUsed = new boolean[size];
}
public boolean indexIsUsed(int ind) {
return isUsed[ind];
}
public boolean allNotUsed(List<Integer> indices) {
// return indices.stream().noneMatch(i -> isUsed[i]); // this line does the same as the loop below
boolean result = true;
for (int idx: indices) {
if (isUsed[idx]) {
result = false;
break;
}
}
return result;
}
public void setIsUsed(List<Integer> indices) {
for (int ind: indices)
setIsUsed(ind);
}
public void setIsUsed(int ind) {
isUsed[ind] = true;
}
}
Using this approach, we are able to construct combinations from numbers that are not used yet, and iterate over the list of numbers starting from a particular position by passing the index while making a recursive call. We can be sure that any of the elements that reside prier to the current position would not be added to the current combination.
Now, a quick recap on recursion.
Every recursive implementation consists of two parts:
Base case - that represents an edge-case (or a set of edge-cases) for which the outcome is known in advance. For this problem, there are two edge-cases:
we've managed to find a combination that gives the target number, i.e.
currentSum == target, and the result would be equal totarget;the end of the list is reached (and the combination doesn't result to the target), the result would be
0(this edge-case resolves automatically by termination condition of theforloop in the recursive case, and therefore no need to treat it separately).
Recursive case - a part of a solution where recursive calls are made and where the main logic resides. In the recursive case we're iterating over the list of numbers and at each iteration step (if the index is not yet used) we are making one or two recursive calls depending on a value of the current element (depending whether we exceed the target or not). In the general, we have two opportunities: either take the current element, or ignore it. The results of these recursive calls would be added together and produce the return value of the recursive case.
Since we need a couple of additional parameters, it's a good practice to create an auxiliary overloaded method (that will be used in the client code) which expects only a list of numbers and a target value and delegates the actual work to the recursive method.
That's how it might look like.
public static int sumRecursively(List<Integer> numbers, int target) {
return sumRecursively(new ArrayList<>(numbers),
new ArrayList<>(),
new CombinationTracker(numbers.size()),
0, 0, target);
}
The actual recursive method:
private static int sumRecursively(List<Integer> numbers,
List<Integer> combination,
CombinationTracker tracker,
int currentIndex,
int currentSum, int target) {
if (currentSum == target && tracker.allNotUsed(combination)) { // base case - a combination has been found
tracker.setIsUsed(combination);
return target;
}
// recursive case
int result = 0;
for (int i = currentIndex; i < numbers.size(); i++) {
int next = numbers.get(i);
if (tracker.indexIsUsed(i)) continue;
if (currentSum + next > target) continue;
// there are two opportunities for each number: either use next number, or ignore it
// add next number
if (next + currentSum <= target) {
List<Integer> newCombination = new ArrayList<>(combination);
newCombination.add(i);
result += sumRecursively(numbers, newCombination, tracker, i + 1, currentSum + next, target);
}
// ignore next number
result += sumRecursively(numbers, new ArrayList<>(combination), tracker, i + 1, currentSum, target);
}
return result;
}
main()
public static void main(String[] args) {
System.out.println(sumRecursively(List.of(1, 3, 4, 5, 6, 6), 12));
System.out.println(sumRecursively(List.of(6, 6, 6, 6, 6, 6), 12));
}
Output:
12
36
Related Topics
Count the Number of Non-Zero Elements of Each Column
Format Date-Time as Seasons in R
Make a File Writable in Order to Add New Packages
Apply() Not Working When Checking Column Class in a Data.Frame
Filtering Rows in R Unexpectedly Removes Nas When Using Subset or Dplyr::Filter
How to Change Stacking Order in Stacked Bar Chart in R
Get Monthly Means from Dataframe of Several Years of Daily Temps
R, Find Duplicated Rows , Regardless of Order
Convert/Export Googleway Output to Data Frame
Update a Dataset After Putting a New Value in the Dt::Datatable
R Subset with Condition Using %In% or ==. Which One Should Be Used
Different Axis Limits Per Facet in Ggplot2
Dplyr::N() Returns "Error: Error: N() Should Only Be Called in a Data Context "
Sort a List of Nontrivial Elements in R
Spacing Between Boxplots in Ggplot2
Different Robust Standard Errors of Logit Regression in Stata and R
Regression (Logistic) in R: Finding X Value (Predictor) for a Particular Y Value (Outcome)