algorithm to sum up a list of numbers for all combinations

Question

I have a list of numbers and I want to add up all the different combinations. For example:

• number as 1,4,7 and 13
• the output would be:

1+4=5
1+7=8
1+13=14
4+7=11
4+13=17
7+13=20
1+4+7=12
1+4+13=18
1+7+13=21
4+7+13=24
1+4+7+13=25

Is there a formula to calculate this with different numbers?

Answer 1

A simple way to do this is to create a bit set with as much bits as there are numbers. In your example 4.

Then count from 0001 to 1111 and sum each number that has a 1 on the set:

Numbers 1,4,7,13:

0001 = 13=13
0010 = 7=7
0011 = 7+13 = 20

1111 = 1+4+7+13 = 25

Answer 2

Here's how a simple recursive solution would look like, in Java:

public static void main(String[] args)
{
    f(new int[] {1,4,7,13}, 0, 0, "{");
}

static void f(int[] numbers, int index, int sum, String output)
{
    if (index == numbers.length)
    {
        System.out.println(output + " } = " + sum);
        return;
    }

    // include numbers[index]
    f(numbers, index + 1, sum + numbers[index], output + " " + numbers[index]);

    // exclude numbers[index]
    f(numbers, index + 1, sum, output);
}

Output:

{ 1 4 7 13 } = 25
{ 1 4 7 } = 12
{ 1 4 13 } = 18
{ 1 4 } = 5
{ 1 7 13 } = 21
{ 1 7 } = 8
{ 1 13 } = 14
{ 1 } = 1
{ 4 7 13 } = 24
{ 4 7 } = 11
{ 4 13 } = 17
{ 4 } = 4
{ 7 13 } = 20
{ 7 } = 7
{ 13 } = 13
{ } = 0

Answer 3

The best-known algorithm requires exponential time. If there were a polynomial-time algorithm, then you would solve the subset sum problem, and thus the P=NP problem.

The algorithm here is to create bitvector of length that is equal to the cardinality of your set of numbers. Fix an enumeration (n_i) of your set of numbers. Then, enumerate over all possible values of the bitvector. For each enumeration (e_i) of the bitvector, compute the sum of e_i * n_i.

The intuition here is that you are representing the subsets of your set of numbers by a bitvector and generating all possible subsets of the set of numbers. When bit e_i is equal to one, n_i is in the subset, otherwise it is not.

The fourth volume of Knuth's TAOCP provides algorithms for generating all possible values of the bitvector.

Answer 4

C#:

I was trying to find something more elegant - but this should do the trick for now...

//Set up our array of integers
int[] items = { 1, 3, 5, 7 };

//Figure out how many bitmasks we need... 
//4 bits have a maximum value of 15, so we need 15 masks.
//Calculated as:
//    (2 ^ ItemCount) - 1
int len = items.Length;
int calcs = (int)Math.Pow(2, len) - 1;

//Create our array of bitmasks... each item in the array
//represents a unique combination from our items array
string[] masks = Enumerable.Range(1, calcs).Select(i => Convert.ToString(i, 2).PadLeft(len, '0')).ToArray();

//Spit out the corresponding calculation for each bitmask
foreach (string m in masks)
{
    //Get the items from our array that correspond to 
    //the on bits in our mask
    int[] incl = items.Where((c, i) => m[i] == '1').ToArray();

    //Write out our mask, calculation and resulting sum
    Console.WriteLine(
        "[{0}] {1}={2}", 
        m, 
        String.Join("+", incl.Select(c => c.ToString()).ToArray()), 
        incl.Sum()
    );
}

Outputs as:

[0001] 7=7
[0010] 5=5
[0011] 5+7=12
[0100] 3=3
[0101] 3+7=10
[0110] 3+5=8
[0111] 3+5+7=15
[1000] 1=1
[1001] 1+7=8
[1010] 1+5=6
[1011] 1+5+7=13
[1100] 1+3=4
[1101] 1+3+7=11
[1110] 1+3+5=9
[1111] 1+3+5+7=16

Answer 5

Here is a simple recursive Ruby implementation:

a = [1, 4, 7, 13]

def add(current, ary, idx, sum)
    (idx...ary.length).each do |i|
        add(current + [ary[i]], ary, i+1, sum + ary[i])
    end
    puts "#{current.join('+')} = #{sum}" if current.size > 1
end    
add([], a, 0, 0)

Which prints

1+4+7+13 = 25
1+4+7 = 12
1+4+13 = 18
1+4 = 5
1+7+13 = 21
1+7 = 8
1+13 = 14
4+7+13 = 24
4+7 = 11
4+13 = 17
7+13 = 20

If you do not need to print the array at each step, the code can be made even simpler and much faster because no additional arrays are created:

def add(ary, idx, sum)
    (idx...ary.length).each do |i|
        add(ary, i+1, sum + ary[i])
    end
    puts sum
end
add(a, 0, 0)

I dont think you can have it much simpler than that.

Answer 6

This Perl program seems to do what you want. It goes through the different ways to choose n items from k items. It's easy to calculate how many combinations there are, but getting the sums of each combination means you have to add them eventually. I had a similar question on Perlmonks when I was asking How can I calculate the right combination of postage stamps?.

The Math::Combinatorics module can also handle many other cases. Even if you don't want to use it, the documentation has a lot of pointers to other information about the problem. Other people might be able to suggest the appropriate library for the language you'd like to you.

#!/usr/bin/perl

use List::Util qw(sum);
use Math::Combinatorics;

my @n = qw(1 4 7 13);

foreach my $count ( 2 .. @n ) {
    my $c = Math::Combinatorics->new(
        count => $count,  # number to choose
        data => [@n],
        );

    print "combinations of $count from: [" . join(" ",@n) . "]\n";

    while( my @combo = $c->next_combination ){
        print join( ' ', @combo ), " = ", sum( @combo ) , "\n";
        }
    }

Answer 7

Mathematica solution:

{#, Total@#}& /@ Subsets[{1, 4, 7, 13}]  //MatrixForm

Output:

{}  0
{1} 1
{4} 4
{7} 7
{13}    13
{1,4}   5
{1,7}   8
{1,13}  14
{4,7}   11
{4,13}  17
{7,13}  20
{1,4,7} 12
{1,4,13}    18
{1,7,13}    21
{4,7,13}    24
{1,4,7,13}  25

Answer 8

You can enumerate all subsets using a bitvector.

In a for loop, go from 0 to 2 to the Nth power minus 1 (or start with 1 if you don't care about the empty set).

On each iteration, determine which bits are set. The Nth bit represents the Nth element of the set. For each set bit, dereference the appropriate element of the set and add to an accumulated value.

ETA: Because the nature of this problem involves exponential complexity, there's a practical limit to size of the set you can enumerate on. If it turns out you don't need all subsets, you can look up "n choose k" for ways of enumerating subsets of k elements.

Answer 9

PHP: Here's a non-recursive implementation. I'm not saying this is the most efficient way to do it (this is indeed exponential 2^N - see JasonTrue's response and comments), but it works for a small set of elements. I just wanted to write something quick to obtain results. I based the algorithm off Toon's answer.

$set = array(3, 5, 8, 13, 19);

$additions = array();
for($i = 0; $i < pow(2, count($set)); $i++){
    $sum = 0;
    $addends = array();
    for($j = count($set)-1; $j >= 0; $j--) {
        if(pow(2, $j) & $i) {
            $sum += $set[$j];
            $addends[] = $set[$j];
        }
    }
    $additions[] = array($sum, $addends);
}

sort($additions);

foreach($additions as $addition){
    printf("%d\t%s\n", $addition[0], implode('+', $addition[1]));
}

Which will output:

0   
3   3
5   5
8   8
8   5+3
11  8+3
13  13
13  8+5
16  13+3
16  8+5+3
18  13+5
19  19
21  13+8
21  13+5+3
22  19+3
24  19+5
24  13+8+3
26  13+8+5
27  19+8
27  19+5+3
29  13+8+5+3
30  19+8+3
32  19+13
32  19+8+5
35  19+13+3
35  19+8+5+3
37  19+13+5
40  19+13+8
40  19+13+5+3
43  19+13+8+3
45  19+13+8+5
48  19+13+8+5+3

For example, a case for this could be a set of resistance bands for working out. Say you get 5 bands each having different resistances represented in pounds and you can combine bands to sum up the total resistance. The bands resistances are 3, 5, 8, 13 and 19 pounds. This set gives you 32 (2^5) possible configurations, minus the zero. In this example, the algorithm returns the data sorted by ascending total resistance favoring efficient band configurations first, and for each configuration the bands are sorted by descending resistance.

Answer 10

v=[1,2,3,4]#variables to sum
i=0
clis=[]#check list for solution excluding the variables itself
def iterate(lis,a,b):
    global i
    global clis
    while len(b)!=0 and i<len(lis):
        a=lis[i]
        b=lis[i+1:]
        if len(b)>1:
            t=a+sum(b)
            clis.append(t)
        for j in b:
            clis.append(a+j)
        i+=1
        iterate(lis,a,b)
iterate(v,0,v)

its written in python. the idea is to break the list in a single integer and a list for eg. [1,2,3,4] into 1,[2,3,4]. we append the total sum now by adding the integer and sum of remaining list.also we take each individual sum i.e 1,2;1,3;1,4. checklist shall now be [1+2+3+4,1+2,1+3,1+4] then we call the new list recursively i.e now int=2,list=[3,4]. checklist will now append [2+3+4,2+3,2+4] accordingly we append the checklist till list is empty.

Answer 11

set is the set of sums and list is the list of the original numbers.

Its Java.

public void subSums() {
    Set<Long> resultSet = new HashSet<Long>();
    for(long l: list) {
        for(long s: set) {
            resultSet.add(s);
            resultSet.add(l + s);
        }
        resultSet.add(l);
        set.addAll(resultSet);
        resultSet.clear();
    }
}

Answer 12

This is not the code to generate the sums, but it generates the permutations. In your case:

1; 1,4; 1,7; 4,7; 1,4,7; ...

If I have a moment over the weekend, and if it's interesting, I can modify this to come up with the sums.

It's just a fun chunk of LINQ code from Igor Ostrovsky's blog titled "7 tricks to simplify your programs with LINQ" (http://igoro.com/archive/7-tricks-to-simplify-your-programs-with-linq/).

T[] arr = …;
var subsets = from m in Enumerable.Range(0, 1 << arr.Length)
              select
                  from i in Enumerable.Range(0, arr.Length)
                  where (m & (1 << i)) != 0
                  select arr[i];

Answer 13

public static void main(String[] args) {
        // this is an example number
        long number = 245L;
        int sum = 0;

        if (number > 0) {
            do {
                int last = (int) (number % 10);
                sum = (sum + last) % 9;
            } while ((number /= 10) > 0);
            System.err.println("s = " + (sum==0 ? 9:sum);
        } else {
            System.err.println("0");
        }
    }

Answer 14

Thanks Zach,

I am creating a Bank Reconciliation solution. I dropped your code into jsbin.com to do some quick testing and produced this in Javascript:

function f(numbers,ids, index,  sum, output, outputid, find )
{
    if (index == numbers.length){
          var x ="";
          if (find == sum) {
              y= output + " } = " + sum + "  " + outputid + " }<br/>" ;
          }
        return;
    }
    f(numbers,ids, index + 1, sum + numbers[index], output + " " + numbers[index], outputid + " " + ids[index], find);
    f(numbers,ids, index + 1, sum, output, outputid,find);
}

var y;

f( [1.2,4,7,13,45,325,23,245,78,432,1,2,6],[1,2,3,4,5,6,7,8,9,10,11,12,13], 0, 0, '{','{', 24.2);
if (document.getElementById('hello')) {
  document.getElementById('hello').innerHTML = y;
}

I need it to produce a list of ID's to exclude from the next matching number.

I will post back my final solution using vb.net

Answer 15

You might be interested in checking out the GNU Scientific Library if you want to avoid maintenance costs. The actual process of summing longer sequences will become very expensive (more-so than generating a single permutation on a step basis), most architectures have SIMD/vector instructions that can provide rather impressive speed-up (I would provide examples of such implementations but I cannot post URLs yet).