Solved

# every possible sum of array elements

Posted on 2003-03-17
Medium Priority
359 Views
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
Question by:romeo201us
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 4
• 4
• 3
• +1

LVL 6

Expert Comment

ID: 8153596
0

LVL 46

Expert Comment

ID: 8153795
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

LVL 6

Expert Comment

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

LVL 46

Accepted Solution

Kent Olsen earned 100 total points
ID: 8154220

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 Comment

ID: 8159539
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

LVL 8

Expert Comment

ID: 8163085
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

LVL 8

Expert Comment

ID: 8163630
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

LVL 8

Expert Comment

ID: 8163632
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 Comment

ID: 8168543
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

LVL 8

Expert Comment

ID: 8170289
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

LVL 46

Expert Comment

ID: 8174691
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 Comment

ID: 8186640
i got it!!
0

Author Comment

ID: 8186665
brilliant idea!!
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were smallâ€¦
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see soâ€¦
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.
###### Suggested Courses
Course of the Month10 days, 11 hours left to enroll