Skip to main content
4 of 4
added 91 characters in body
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

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.

Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152