How to 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).

How many combinations are there for the 5-element case? How many combinations are there for the 4-element case? Do those numbers look familiar? — Oliver Charlesworth, Jan 14 '12 at 02:09
possible duplicate of [How to find all possible subsets of a given array?](http://stackoverflow.com/questions/679203/how-to-find-all-possible-subsets-of-a-given-array) — Oliver Charlesworth, Jan 14 '12 at 02:10
Think of one-, two-, three-, etc element combinations as a separate case. Write the code to print out all the combinations of just one element (it should be easy). Then try to write the code for combinations of two elements, and if you can't make it work show us what you did try. — Jon, Jan 14 '12 at 02:10
@OliCharlesworth The pattern is very similar, but just very difficult to explain it out. :/ — William Tio Wee Leong, Jan 14 '12 at 02:18
@Jon: Assuming the specific order of combinations doesn't matter, there's a **much** easier way to generate all the combinations than explicitly isolating all the 1-element cases, then all the 2-element cases, etc. (think binary counter). — Oliver Charlesworth, Jan 14 '12 at 02:23
Some insight- the case with a single letter (n = 1) is trivial. Try to solve this problem for the nth case in terms of the preceding case. Does this approach sound familiar? — Alexander Kondratskiy, Jan 14 '12 at 02:23
Dup of [combinations algorithm](http://stackoverflow.com/questions/2506119/), [which is the best way to generate choices out of a given set of numbers?](http://stackoverflow.com/questions/3405511/). — outis, Jan 14 '12 at 02:35
@OliCharlesworth: I 'm suggesting an approach that will allow (at least IMHO) the OP to slowly evolve a solution that they can understand. Revelation-like solutions can only help exceptional students; others will tend to just memorize and reproduce until the exam is past. In my eyes this case here is a matter of teaching the basics, although of course you are spot on in pointing out the better solution technology-wise. — Jon, Jan 14 '12 at 03:25
The keyword here is `powerset` or `superset`. You're searching for the supersets sums. — user unknown, Jan 14 '12 at 08:58
Hint: If you know how to figure out all the combinations of arrays of size 1 and 2, you should be able to easily use that knowledge to figure it out for an array of any size! I don't think you'll get any of us to give you a step-by-step answer, because we want you to actually do your homework. :) — brendanw, Jan 14 '12 at 03:18

score 2 · Accepted Answer · answered Jan 14 '12 at 02:25

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.

score 0 · Answer 2 · answered Jan 14 '12 at 03:45

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.

Except from the headline, it is pretty clear, that not the number of elements in the superset is searched for, but the sums of elements. — user unknown, Jan 14 '12 at 06:59
whoever you are, having worked with quite a number of people over the decades who were ESL i would never make that assumption -- which is precisely why i made the distinction and provided both. improved precision of asking is one possible outcome, without the annoying delay of having to round-trip the clarification step. fwiw — kai26873, Jan 16 '12 at 01:19

score 0 · Answer 3 · answered Jan 14 '12 at 07:40

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.

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

3 Answers3