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


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.
  • $\begingroup$ Store the original index of each element before sorting. Use the data structure from the appendix of my paper arxiv.org/abs/1504.04931 to break ties quickly. $\endgroup$ Nov 1 '15 at 18:19
  • $\begingroup$ In view of my answer below, please notice that the proposed algorithm is not polynomial in the size of the input. The input size here is a polynomial in $|T|$ and $\log k$ (not $k$). $\endgroup$ Oct 11 '16 at 14:45
  • $\begingroup$ Correct, of course. There's still a big gap between hardness for polylog$(k)$ and this $O(k)$ algorithm that it would be interesting to tighten. $\endgroup$ Oct 11 '16 at 17:15
  • $\begingroup$ Output all subset up to the $k$th one is only $O(k \log k)$, because output a set of size $t$ implies all its subsets are also in the output, so the largest set has size $\log k$. $\endgroup$
    – Chao Xu
    Apr 21 '17 at 7:28

I'm afraid solving your problem in polynomial time is not possible unless P=NP. (Notice that the input size here is a polynomial in $|T|$ and $\log k$, but not $k$.)

If one can solve your problem in polynomial time, then using such solution algorithm $P(T,k)$ and binary search (in the virtual array of subsets of $T$ sorted by their sums, where $k$-th element is accessed with $P(T,k)$), it would be possible to solve the Subset Sum Problem in polynomial time as well. But the latter problem is NP-complete.

  • $\begingroup$ @D.W.: First, the question does not explicitly ask "for an algorithm whose running time is polynomial in $k$" (such algorithm would not be necessarily polynomial in the size of the input). Second, I proved that if there is a polynomial-time algorithm (in the size of the input, which is polynomial in $\log k$, not $k$), then there would be one for the subset sum problem. Third, the algorithm proposed in the other answer is not polynomial as it constructs a tree on all subsets of the input set. $\endgroup$ Oct 11 '16 at 14:20

Not the answer you're looking for? Browse other questions tagged or ask your own question.