Algorithm wanted: Enumerate all subsets of a set in order of increasing sums I'm looking for an algorithm but I don't quite know how to implement it. More importantly, I don't know what to google for. Even worse, I'm not sure it can be done in polynomial time.
Given a set of numbers (say, {1, 4, 5, 9}), I want to enumerate all subsets of this set (its power set, really) in a certain order: increasing sum of the elements.
For example, given {1, 4, 5, 9}, the subsets should be enumerated in this order, "smaller" sets first:

{} = 0
{1} = 1
{4} = 4
{5} = 5
{1, 4} = 5
{1, 5} = 6
{9} = 9
{4, 5} = 9
{1, 9} = 10
{1, 4, 5} = 10
{4, 9} = 13
{5, 9} = 14
{1, 4, 9} = 14
{1, 5, 9} = 15
{4, 5, 9} = 18
{1, 4, 5, 9} = 19

This feels like some unholy mix between a breadth-first search and a depth-first search, but I can't wrap my head around the proper way to mix these two search strategies.
My search space is very large ($2^{64}$ elements) so I can't precompute them all up-front and sort them. On that note, I also don't need to enumerate the entire search space -- the smallest 4,096 subsets is fine, for example.
Can anyone give any pointers or even any clues to google for? Many thanks.

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$).


*

*$N$ consists of the numbers in the original set; i.e., $N = [1, 4, 5, 9]$ in your example.

*$L$ is the list of subsets found so far.  

*$A[i]$ contains the subset that $N[i]$ is currently considering.

*$S[i]$ is the sum of the elements of subset $i$ in $L$.


Algorithm:


*

*Initialize $N$ to numbers in the original set, all entries of $A$ to $0$, $L[0] = \{\}$, $S[0] = 0$.  Let $j = 1$.

*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.

*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.)

*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$.)

*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$.
