How to do list all the possible sums of combinations in an array for c++?

Question

I have my homework assignment and I have no idea how to start with the code for this kind of Problem.

Let say I have an integer array with consist of n elements,

[A][B][C][D][E] (We have 5 elements for example)

I want to list out all the sum of possibility such that I want to print out the sum of all combination (ABCDE, ABCD, ABCE, ACDE, BCDE, ABC, ABD, ABE, ACE, ADE, BDE, CDE, AB, AC, AD, AE, BC, BD, BE, CD, CE, DE, A, B, C, D and E)

Another example would be 4 elements in an array ([A][B][C][D])

I want to list all sum of combination of (ABCD, ABC, ABD, ACD, BCD, AB, AC, AD, BC, BD, CD, A, B, C and D).

I hope you all manage to understand my question. I need help for it and I do not know how to do with it?

Answer 1

Well, here's a simple rule to follow:

The set of all combinations of "ABCDE" is composed of those combinations which contain (and thus start with) "A" and those which don't contain "A". In both cases, all combinations of "BCDE" can occur. Of course, combinations of "BCDE" can be treated in the same way.

Answer 2

When you say "list out all the sum of possibility" do you mean you want to know how many combinations are actually possible?

If so, then search on combinations of N items taken K at a time; there are pages on this very site addressing this problem. You would then simply add the number of combinations of (by 5) + (by 4) + (by 3) + (by 2) + (by 1) to get your total "sum of possibilities".

Or do you mean you have an array of values and you literally want to print out the different sums represented by different combinations of the elements? In that case you need to actually enumerate all the combinations and evaluate the sums.

So given an array of { 1, 2, 3, 4, 5 } you can encode this as "A", "B", "C", "D", "E". Examples of tuples would be:

• ABCDE = 1+2+3+4+5
• ABE = 1+2+5
• BCE = 2+3+5

etc, where you use the encoded enumeration to select the addends for your sum. Note that deciding whether to allow or disallow duplicates (i.e., is "DE" different from "ED") will have a very large effect on your results; in most cases this will probably not be what you want.

Answer 3

If you have 3 elements, you may imagine each element placed at a certain position from 1 to 3 (or 0 to 2) and a boolean array representing whether the element is contained in a certain set.

ABC remark
--- ---------------------
000 no element in the set
001 one element, C
010 one element, b
100 ...
011 two elements, b and c
...
111 all elements contained

Now if you calculate the number of solutions, which is 2³ in this case, and generate a function, which does a mapping from a binary representation to a set, from 011 to (b, c) for example, then you can easily program a loop, which iterates from 0 to max-1 and returns all sets, produced by your mapping function.