- #1

Moni

- 181

- 1

- TL;DR Summary
- Generating Subsets of a Multiset in Ascending Order of the Sums of the Elements of the Sub(multi)set

**Summary:**Generating Subsets of a Multiset in Ascending Order of the Sums of the Elements of the Sub(multi)set

I am trying to come up with an algorithm where you can generate combination from a set in a order such that their sums are in increasing order. This set has to be a multiset i.e. repetition allowed.

For example you have a set S = {1,2,2,3,4,5,5}

So, rather than generating all the combinations based on number of items (say start with 1 and 2 items and finally all 7) I want to figure them out in this order:

{1}, {2}, {2}, {1,2}, {1,2}, {3}, {1,3}, {2,2}, {4}.....{1,2,2,3,4,5,5}

Why this order: Well taking sum of these subsets we can see:

{1}, {2}, {2}, {3}, {3}, {3}, {4}, {4}, {4}.....{22}

Do you know any algorithm which can do it efficiently?