Skip to main content
1 of 3
Ood
  • 81
  • 4

Generating all Possible Subsets in Order of Sum

Given a set of positive integers, I am looking for method to algorithmically generate all possible subsets in order of their sum. Because the the count of possible subsets is exponential ($2^n$), it is not feasible to brute-force them and then sort. Instead, the solution would generate one answer at a time, starting with smallest sum (i.e. an online algorithm).

Here's an example:

$$A=\{1,2,10\}$$

And the expected results:

$$S_1=\{\}$$ $$S_2=\{1\}$$ $$S_3=\{2\}$$ $$S_4=\{1,2\}$$ $$S_5=\{10\}$$ $$S_6=\{1,10\}$$ $$S_7=\{2,10\}$$ $$S_8=\{1,2,10\}$$

This problem seems to be related to the Knapsack problem and the Subset sum problem. It is also related to this question, to which there are unfortunately no answers. In my specific case the previous solutions are known and the overall time complexity is not the issue, but calculating the answers in the correct order. This is why I hope there is a solution that runs in polynomial time per iteration, but in $O(2^n)$ for all answers.

If someone could confirm whether it is possible or point me in the right direction it would be greatly appreciated.

Ood
  • 81
  • 4