# Get $n^{\mathrm{th}}$ element of sorted subset sums

I have a sorted multiset (size < 100, real valued) and want to determine the $$n^{\mathrm{th}}$$ largest of all possible subset sums (including multiplicity in the sums).

Attempt at solving :

I have been looking at ordering the sums starting with the unbounded knapsack problem (UKP) with equal weights to find the sets of each size with minimal sum, then establishing a rule for determining the order of corresponding sets after replacing elements, in the hope that this would reduce the number of comparisons. However, this doesn't seem to simplify the problem.

• math.stackexchange.com/questions/89419/… Dec 7, 2020 at 22:03
• Thank you for that reference. It does accomplish what I'm looking for, but I can't reach large values in the search space with that speed. Is there any chance I could skip over a chunk of subsets without explicitly finding and summing them? Dec 7, 2020 at 22:21
• The problem is NP-hard: if we could solve your problem efficiently, it would be easy to solve the subset sum problem too (using binary search). I don't know whether there is a way to take advantage of the known algorithms for subset sum to solve this for the a multiset of size 100; I haven't figured out a way, but maybe someone else will have some ideas.
– D.W.
Dec 8, 2020 at 0:00
• I see, you have clarified the relation between my problem and subset sum and a lower bound on time complexity is already very good to know, thank you. Dec 8, 2020 at 0:06