• Status: Solved
• Priority: Medium
• Security: Public
• Views: 367

# every possible sum of array elements

i am working on a program which makes use of every possible sum of array elements. I also put into consideration every array element. I used recursion but i could generate only half of them.
if the input is an array with 6 elements: say Array[6] then
i want the output to look like this:
0 01 02 03 04 05 012 013 014 015 023 024 025 034 035 045 0345 0123 0124 0125 0134 0135 0145 0234 0235 0245  01234 01235 01245 01345 02345 012345
this are the combination of the indices.

help!!
thanks

0
romeo201us
• 4
• 4
• 3
• +1
1 Solution

Commented:
0

Data Warehouse Architect / DBACommented:
You're dealing with combinations, not permutations, so there's a really easy, quick, and effective way to get your answer.

First, the number of answers gets big very quickly.  Basically, there are 2^n-1 combinations of elements so for our purposes let's assume that n is rational.  (2^32 is in the billions, let's stop way short of there.)

void GenerateCombinations (int Elements)
{
int idx;
int Limit;

Limit = 1 << Elements;
for (idx = 0; idx < Elements; idx++)
{
/* Evaluate and Print */
}
}

Replace the comment /* Evaluate and Print */ with simple code to interrogate idx for the "1 bits".  If the bit is on, print the corresponding array element.  End with a new-line.

As idx increments, the result will be:

idx     Result
00000001  A
00000010  B
00000011  A B
00000100  C
00000101  A C
... etc

Good Luck,
Kdo
0

Commented:
Kdo - I thought he wanted the SUM of every possible combination of array elements...
0

Data Warehouse Architect / DBACommented:

Good Catch.

Instead of my stated "print the corresponding array element", the correct action should be:

for (idx = 0; idx < Elements; idx++)
{
Sum = 0;
/* Evaluate and compute Sum via:
Sum += ArrayElement[] */
fprintf (stdout, "%d\n", Sum);
}

Damn these Mondays.....

Kdo
0

Author Commented:
thanks kdo,
i really got the idea
the first thing which came to my mind was just using loops and recursion, i didn't make use of bit operations.
it is long , but i guess it is possible to do it like this too:
{0 1 2 3 4 5}
then
{0} {1 2 3 4 5} make every possible combination
{0 1} { 2 3 4 5}  sort of multiplication u know
{0 2} {3 4 5}
--- go on like that ---but too long.

i would be delighted if u can come up with such ideas!!
thanks
0

Commented:
if u need performance then KDO gave u best solution,
and trust us ( not US of 'USA') , thats not long to implement or execute either.

still u wanna go with recursion then i have something for you.
also one more point u might be interested in knowing,
ur approach of generating combination of indices
lets say for 0 1 and 2   combinations goes
0 1 2 01 02 12 012

this again will come to the stage where KDO's solution  starts u ( his solution already has combinations generated in the form of integers' binary notation)
all u need to do is sum-up the integers.

0

Commented:
if u r interested only in the SUMS and not in 'what comprises the sum' then here is something u can do,

take another array of integers of the length of 2^n -1
( u need to malloc it dynamically)

int arr[MAX];
int *sums, nSums;
int count, i, len, j;

memset(arr,0,sizeof(int)*MAX);
arr[0] = 1;  arr[1] = 2;  arr[2] = 3;  arr[3] = 4;

len = 4; //number of elements
nSums = (1 << len) - 1;
sums = (int *) malloc (sizeof (int) * nSums);

memset(sums,0,sizeof(int)*nSums);
count = 0;               //number of sums calculated as yet
for (i = 0; i < len; i++)
{

sums[count] = arr[i];
for (j = 0; j < count ; j++)
{
sums[count + j+1] = sums[j] + arr[i];
}
count = count + count + 1;
}
nSums = count;

for (i = 0; i < nSums; i++)
printf ("sums[%d]=%d\n", i, sums[i]);
0

Commented:
this u can modify to generate indices also .. in that case .. instead of sums .. u will have to make strings and concatanate the new indices.. to already existing indices,
that we will leave for u as an exercise
0

Author Commented:
i am thankful to u , ashayxx.
well ashayxx, actually i will need the indices. U know the problem came to my mind like this:
"Assume a certain person has ,say, \$100 -- u don't like the "\$" part -- do u?? - ---- any way, so he comes to a super-market and wants to buy any number of items, and preferably of different type--as long as the sum accumulates to \$100 , if not to the nearest digit below 100 -- so that he can affort it.how would u confront this?"

i am very thankful , u gave me a nice solution. KDO's solution is very amazing. i loved it.
0

Commented:
i said
>>this u can modify to generate indices also

just in case KDO's solution is a bit hot to handle . u can modify mine .. to generate combination of indices also ..
any ways still it wont beat KDO's :)
0

Data Warehouse Architect / DBACommented:
Taking akshayxx's methodology one step further....

Build two arrays of length 2^n.  (2^n-1 will contain all of the sums, the extra entry is because the null set may have to be accounted for.)

Take the first element in your input array and add it to every other element in the Result[] array.  (Don't add to the first element, add to the second, etc..)  Every time you add the element to the Result[] array, add 1 to the second array at the same offset.

Now take the second element in your input array and add it to the Result[] array, but this time, skip the first two elements, add to the next two, skip two more, add to the next two, etc...  This time add 2 to the second array every time you add to Result[].

Repeat with the third element, but the patter is 4s.  Skip the first 4, add to the next 4, skip the next 4, add to the next 4, etc.  This time you add 4 to the second array.

Repeat for every element in the source array.  Every time you advance to the next element, the size of the pattern doubles (the number of consecutive items to skip and the quantity to add to the second array double with each successive source element).

Now, assume that the source array contains the values A, B, C, D, E, and F.  (I know -- they should be numeric.)  Here's what is now contained in the two arrays:

Second  Result
000000  0 (null)
000001  A
000010  B
000011  A + B
000100  C
000101  A + C
000110  B + C
000111  A + B + C
001000  D
001001  A + D
....
111110  B + C + D + E + F
111111  A + B + C + D + E + F

We have both calculated all possible sums.  This most recent test "connects the dots" and shows how the algorithms relate.

However, it is my assumption (and ultimately, belief) that your instructor will eventually want to see this written recursively.  That's not tough, either.

Kdo
0

Author Commented:
i got it!!
0

Author Commented:
brilliant idea!!
0

## Featured Post

• 4
• 4
• 3
• +1
Tackle projects and never again get stuck behind a technical roadblock.