How to enumerate all k-combinations of a set by sum?

2
votes

Suppose I have a finite set of numeric values of size n.

Question: Is there an efficient algorithm for enumerating the k-combinations of that set so that combination I precedes combination J iff the sum of the elements in I is less than or equal to the sum of the elements in J?

Clearly it's possible to simply enumerate the combinations and sort them according to their sums. If the set is large, however, brute enumeration of all combinations, let alone sorting, will be infeasible. If I'm only interested in obtaining the first m << choose(n,k) combinations ranked by sum, is it possible to obtain them before the heat death of the universe?

1
algorithmcombinatorics

1 Answers

5
votes

There is no polynomial algorithm for enumerating the set this way (unless P=NP).

If there was such an algorithm (let it be A), then we could solve the subset sum problem polynomially:

  1. run A
  2. Do a binary search to find the subset that sums closest to the desired number.

Note that step 1 runs polynomially (assumption) and step 2 runs in O(log(2^n)) = O(n).

Conclusion: Since the Subset Sum problem is NP-Complete, solving this problem efficiently will prove P=NP - thus there is no known polynomial solution to the problem.

Edit: Even though the problem is NP-Hard, getting the "smallest" m subsets can be done on O(n+2^m) by selecting the smallest m elements, generating all the subsets from these m elements - and choosing the minimal m of those. So for fairly small values of m - it might be feasible to calculate it.