Hello everyone 
I want to calculate all the combinations between the values of an array[].
I have an array with numbers of type long. The number of values (the lenght of the array) is not fixed, but can vary between 1 and 15.
For example a simple array with 3 values {5,9,3}
The combinations that i want to calculate are:
5+9
5+3
9+3
5+9+3
What is a good way to calculate al those combinations?
Thanks in advance.
Corneel
try this function out:
long TotalValue(long * LArray) {
 long Total = 0;
 int ArrayLength;
 ArrayLength = sizeof(LArray)/sizeof(long);
 if (!ArrayLength)return (0);
 for (int Position = 0; Position < ArrayLength; Position++) {
  Total += LArray[Position];
 }
 return (Total);
}
Z
Thanks for your reaction.
But your function calculates only the total sum. Or am i wrong?
I want to know the sum of every possible combination.
So if there are 10 values in my array, I want to know the sum of each 1098765432*1 combinations or 3.628.800 combinations.
You want a function written for you, or are you going to provide some effort?
Corneel:
So if there are 10 values in my array, I want to know the sum of each 1098765432*1 combinations or 3.628.800 combinations.
This is the number of all 10-tuples, which all have the same sum.
Multiply both numbers (LL could be useful) and you are done.
You might google permutations and combinations as defined in a statistical sense.
In order to not do your whole work Try to understand what the following algorithm does.
this one works with an array made of elements of 1 character and shows all the possible sums
There is NO memory overflow testing
char array[] = {'a', 'b', 'c','d','e'};
const unsigned int n = sizeof(array) / sizeof(array[0]);
char ** solutions;
unsigned int combine(unsigned int nb)
{
 if (nb == 1) return 1;
 else return 2 * combine(nb - 1) + 1;
}
int addToList(char c, int top)
{
 top++;
 *(solutions + top) = (char *) malloc(2 * sizeof(char));
 (*(solutions + top))[0] = c;
 (*(solutions + top))[1] = '\0';
 for (int i = 0; i < top; i++) {
  int l = strlen(*(solutions + i));
  *(solutions + top + i + 1) = (char *) malloc(l + 3 * sizeof(char));
  strcpy(*(solutions + top + i + 1), *(solutions + i));
  (*(solutions + top + i + 1))[l] = '+';
  (*(solutions + top + i + 1))[l+1] = c;
  (*(solutions + top + i + 1))[l + 2] = '\0';
 }
 return top + top;
}
void setup() {
 int top;
 Serial.begin(115200);
 unsigned int total = combine(n);
 Serial.print("Nb Solutions = "); Serial.println(total);
 solutions = (char **) malloc(total * sizeof(char *));
 top = -1;
 for (int i = 0; i < n; i++) {
  top = addToList(array[i], top);
 }
 for (int i = 0; i < total; i++) {
  Serial.println(*(solutions + i));
 }
}
void loop() {}
this will give you an output as
Nb Solutions = 31
a
b
a+b
c
a+c
b+c
a+b+c
d
a+d
b+d
a+b+d
c+d
a+c+d
b+c+d
a+b+c+d
e
a+e
b+e
a+b+e
c+e
a+c+e
b+c+e
a+b+c+e
d+e
a+d+e
b+d+e
a+b+d+e
c+d+e
a+c+d+e
b+c+d+e
a+b+c+d+e
seems close enough to what you described I think. give it a try (console needs to be at 115200 bauds)
Combinations usually means a given number of terms chosen from the array - eg, all combinations of 3 choices over 10. What you are desrcribing- you want both 5+9 and also 5+9+3 is simply the power set.
Easy way to do thins is to iterate a number from 0 to 2^n, and use the bits in it to choose the values.
If you want the distinct values, make an array of boolean whose length is equal to the sum of all the values (plus one). As you calculate each sum, set the corresponding value in your array of boolean.
But there's a better way.
Lets say you have a set of numbers and have calculated all the distinct sums. If you introduce a new number (say, 5), then the new array of distinct sums is simply the union of the current set and the set of all those numbers plus 5.
Observe that you can start by setting zero to true - the result of adding none of the numbers.
int numbers[]; // whatever
const int N; // number of numbers
boolean sums[BIGGEST_POSSIBLE_SUM + 1];
sums[0] = true;
for(i = 0; i < N; i++) {
  // very important to count backwards here
  for(int j = BIGGEST_POSSIBLE_SUM - numbers[i]; j >= 0; j++) {
   if(sums[j]) sums[j + numbers[i]] = true;
  }
}
After doing this, sums[] will be true wherever the sum exists.
You can speed this up a little by keeping track of largest_sum_so_far.
If you want the distinct values, make an array of boolean whose length is equal to the sum of all the values (plus one). As you calculate each sum, set the corresponding value in your array of boolean.
This is the approach taken in the algorithm I offered above. It's a bit more tricky to play with cstrings to have an interesting display but is quite trivial indeed with a number as we know upfront the memory it's going to use (no need for malloc())
So if there are 10 values in my array, I want to know the sum of each 1098765432*1 combinations or 3.628.800 combinations.
By the way there are not factorial of n possiblilies... as you have seen with your example with 3 values {5,9,3} you have 7 (not 4 because you forgot the numbers by themselves) possibilities - see my combine() function for the calculation V0 = 1 (with 1 value in the array), and at position n (With n+1 elements in the array) you have Vn possibilities = 2*Vn-1+1 because addition is commutative so order does not matter (combination versus permutation)
Note that I've been lazy and not memory conscious using recursion in my function while arithmetico-geometric series have an easy expression in one formula - here it would be, with n+1 elements in the array (series starts with 1 element in the array at V0=1):
Vn = 2n*(1-r)+r with r = 1/(1-2) = -1 so
Vn = 2n+1-1
Ex: 3 elements => rank n=2 => 23-1 = 7
If you want to exclude singletons (just one value, no addition) then you need to remove the number of elements from that calculation and With n+1 elements in the array, the formula becomes
Vn = 2n+1-n-2
Ex: 3 elements => rank n=2 => 23-2-2 = 4