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.