Algorithm wanted: Enumerate all subsets of a set in order of increasing sums

Solution 1:

Here's an algorithm. The basic idea is that each number in the original set iterates through the list of subsets you've already found, trying to see if adding that number to the subset it's currently considering results in the smallest subset sum not yet found.

The algorithm uses four arrays (all of which are indexed starting with $0$).

1. $N$ consists of the numbers in the original set; i.e., $N = [1, 4, 5, 9]$ in your example.
2. $L$ is the list of subsets found so far.
3. $A[i]$ contains the subset that $N[i]$ is currently considering.
4. $S[i]$ is the sum of the elements of subset $i$ in $L$.

Algorithm:

1. Initialize $N$ to numbers in the original set, all entries of $A$ to $0$, $L[0] = \{\}$, $S[0] = 0$. Let $j = 1$.
2. For iteration $j$ find the minimum of $S[A[i]] + N[i]$ over all numbers $N[i]$ in the original set. (This finds the subset with smallest sum not yet in $L$.) Tie-breaking is done by number of elements in the set. Let $i^*$ denote the argmin.
3. Let $L[j] = L[A[i^*]] \cup \{N[i^*]\}$. Let $S[j] = S[A[i^*]] + N[i^*]$. (This updates $L$ and $S$ with the new subset.)
4. Increase $A[i^*]$ to the next item in $L$ that has no number larger than $N[i^*]$. If there is none, let $A[i^*] =$ NULL. (This finds the next subset in $L$ to consider for the number $N[i^*]$ just added to an existing subset in $L$ to create the subset just added to $L$.)
5. If all entries in $A[i]$ are NULL, then stop, else increment $j$ and go to Step 2.

For example, here are the iterations for your example set, together with the subset in $L$ currently pointed to by each number.

Initialization:     
{}   1, 4, 5, 9

Iteration 1:    
{}   4, 5, 9
{1}  

Iteration 2:  
{}   5, 9
{1}  4 
{4}

Iteration 3:  
{}   9
{1}  4, 5
{4}
{5}

Iteration 4:  
{}   9
{1}  5
{4}
{5}
{1,4}

Iteration 5:  
{}   9
{1}  
{4}  5
{5}
{1,4}
{1,5}

Iteration 6:  
{}   
{1}  9
{4}  5
{5}
{1,4}
{1,5}
{9}

Iteration 7:  
{}   
{1}    9
{4}  
{5}
{1,4}  5
{1,5}
{9}
{4,5}

Iteration 8:  
{}   
{1}    
{4}    9
{5}
{1,4}  5
{1,5}
{9}
{4,5}
{1,9}

Iteration 9:  
{}   
{1}    
{4}    9
{5}
{1,4}  
{1,5}
{9}
{4,5}
{1,9}
{1,4,5}

And the rest of the iterations just involve adding $9$ successively to each subset already constructed that doesn't include $9$.

Solution 2:

(Too long for a comment.)

Nijenhuis and Wilf's Combinatorial Algorithms details an algorithm for enumerating all the subsets of a given set, based on the Gray code (there is also a modification that makes it produce the subsets lexicographically). The book can be downloaded for free from the link I gave. You can download the FORTRAN routines NEXSUB() and LEXSUB() from Skiena's webpage. Some modification would be needed to have it output results in your desired order.