I have an array of integers T[N] indexed from 1. For example T[1] = 1, T[2] = 4, T[3] = 5, T[4] = 9. Let's enumerate all subsets of this set in a certain order: increasing sum of the elements. In case of a tie, we compare the sorted lists of indexes of numbers in subsets.


For example:



> 
> 1. {} = 0 indexes: 0
> 2. {1} = 1 indexes: 1
> 3. {4} = 4 indexes: 2
> 4. {1, 4} = 5 indexes: 1, 2
> 5. {5} = 5 indexes: 3
> 6. {1, 5} = 6 indexes: 1, 3
> 7. {4, 5} = 9 indexes: 2, 3
> 8. {9} = 9 indexes: 4
> 9. {1, 4, 5} = 10 indexes: 1, 2, 3
> 10. {1, 9} = 10 indexes: 1, 4
> 11. {4, 9} = 13 indexes: 2, 4
> 12. {1, 4, 9} = 14 indexes: 1, 2, 4
> 13. {5, 9} = 14 indexes: 3, 4
> 14. {1, 5, 9} = 15 indexes: 1, 3, 4
> 15. {4, 5, 9} = 18 indexes: 2, 3, 4
> 16. {1, 4, 5, 9} = 19 indexes: 1, 2, 3, 4
> 
> 
> 


There were 3 ties at: 7-8, 9-10, 12-13, so we compared lists of indexes lexicographically.


What I want to do, is to find $k$-th subset. What is the fastest way to do this, assuming that both N and K are less than $10^6$? I know how to do this in quadratic time.


I assume that all numbers are positive and some of them may be equal.


Question is inspired by this <https://math.stackexchange.com/questions/89419/algorithm-wanted-enumerate-all-subsets-of-a-set-in-order-of-increasing-sums>



$k$-th subset in order of increasing sum
Since this is MathOverflow I'll give you the mathematical answer rather than the practical answer. I'll assume all numbers are positive; otherwise minor modifications would be needed to handle negative numbers. Also, I'm taking literally your request for the $k$th subset alone, rather than for all subsets up to that one; otherwise just the time to write them all down could be quadratic.


* Sort the input numbers
* Define a tree on the nonempty subsets, where the root is the singleton consisting only of the first element, the left child of a set whose maximum element is $i$th in the sorted input list is obtained by replacing that element by element $i+1$, and the right child is obtained by including element $i+1$ without removing any existing element. This tree contains all nonempty subsets (exactly once each) and is heap-ordered.
* To make tree operations fast, represent each set implicitly by a triple of (its parent, the operation that was used to create it, its sum). In this way each set can be represented in $O(1)$ space and it takes $O(1)$ time to find its children.
* Find the $k$ smallest elements of the heap-ordered tree using the $O(k)$-time algorithm in "An optimal algorithm for selection in a min-heap", Frederickson, *Inf. & Comput.* 1993 (this is the part that's more theoretical than practical. In practice you could do a best-first search using a binary heap in time $O(k\log k)$, or maybe an integer priority queue if you know that the sums you're going to get are small).
* If you need to, decode the $k$th set from its compact representation into an explicit list of elements, by backtracking through the tree to find the sequence of operations that created this set and then applying those operations to the initial singleton set.


