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:

{} = 0 indexes: 0

{1} = 1 indexes: 1

{4} = 4 indexes: 2

{1, 4} = 5 indexes: 1, 2

{5} = 5 indexes: 3

{1, 5} = 6 indexes: 1, 3

{4, 5} = 9 indexes: 2, 3

{9} = 9 indexes: 4

{1, 4, 5} = 10 indexes: 1, 2, 3

{1, 9} = 10 indexes: 1, 4

{4, 9} = 13 indexes: 2, 4

{1, 4, 9} = 14 indexes: 1, 2, 4

{5, 9} = 14 indexes: 3, 4

{1, 5, 9} = 15 indexes: 1, 3, 4

{4, 5, 9} = 18 indexes: 2, 3, 4

{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