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