all possible summes of array's elements?

Question

how can i find them using c?
for 1 2 3: 1+2,1+3,2+3
and how can i track indexes
of elements on the current iteration
of calculating the sum?
Thanks a lot!

Answer 1

For an array of N terms to sum, I'd create an array of 2^N in size, which is the size of all possible sums of N terms.

/* Source values */
S_SIZ = 5;
int src_vals[S_SIZ];
/* set src_vals[0] to [4] here */

/* Sum values */
int T_SIZ = 1 << S_SIZ; /* 2^S_SIZ */
int sums[T_SIZ];
/* initialize all sums[] values to 0 here */

for (i=0; i for (j=0 i if (j & (1 << i)) sums[j] += src_vals[i];
}
}

You'd use the binary representation of J to decide whether to include the I'th element in the sum.

So...
000b: sums[0] would = 0
001b: sums[1] would be src_vals[0]
010b: sums[2] would be src_vals[1]
011b: sums[3] would be src_vals[0] + src_vals[1]
100b: sums[4] would be src_vals[2]
101b: sums[5] would be src_vals[2] + src_vals[0]
110b: sums[6] would be src_vals[2] + src_vals[1]
111b: sums[7] would be src_vals[2] + src_vals[0] + src_vals[1]
...etc.

Any value in "sums", with its index written out in binary format, would have a "1" bit for every corresponding element of the source values that was added to it.

Note that this assumes you want all possible sums (e.g, for 1,2,3: 0, 1, 2, 3, 1+2, 2+3, 1+3, 1+2+3). If you only want sums of PAIRS of numbers, you'd make an array of N*(N-1)/2 and populate it differently.

=============================
Assuming the other problem (PAIRS of numbers only), I'd create an array of int[][3], where [x][0] was the sum, [x][1] was the index of the first term that went into the sum, and [x][2] was the index of the second term:

int T_SIZ = (S_SIZ * (S_SIZ - 1)) / 2;
int **sums = /* allocate T_SIZ * sizeof (int *) */

int t_idx = 0;
for (i=0; i for (j=i+1; i sums[t_idx] = /* allocate 3 * sizeof (int) */
sums[t_idx][0] = src_vals[i] + src_vals[j];
sums[t_idx][1] = i;
sums[t_idx][2] = j;
t_idx++;
}
}

You could use just a single array of integers for the sums, and work backward from the index to the original i and j values, but unless memory was a huge constraint, it wouldn't be worth the effort and maintenance headaches.

PS - Regarding the response below, I don't think memory is a limitation for this particular exercise. If the original collection has 30 numbers, printing a billion sums and expecting someone to look through them isn't a whole lot more useful than using 4Gb of RAM. The "improvement" almost certainly falls over when the original set hits 31 or at best 32 numbers, due to doing bitwise operations on (signed) ints, anyway.

Answer 2

The problem with the answer above, is that the 2^n array is going to be huge for even moderately large values of n.

Try this:

long array[n] = {...}; // put your n values here

for( long selector = 0; selector< 2**n; selector++)
{
long total = 0;
for(int i = 0; i < n; i++)
{
// if the nth bit of the selector is 1, add the nth element of the array
if(0 != (selector >> i) & 0x1)
{
total += array[n]
}
}
// print or whatever your total.
}

// As selector counts up, you run through all the possible combinations of n bits, which give you all possible totals.