CODEWITHSUNDEEP
algorithmsubset-sum
john Stilkowicz
john Stilkowicz

Reputation: 297

equal k subsets algorithm

does anyone know a good and efficient algorithm for equal k subsets algorithm ? preferably c or c++ which could handle a 100 element vector maybe with a complexity and time estimation

ex. 9 element vector

x = {2,4,5,6,8,9,11,13,14}

i need to generate all k=3 disjoint subsets with sum = 24 the algorithm should check if there are k disjoint subsets each with sum of elements 24, and list them in ascending order(in subset and between subsets) or to see if the solution doesn't exists

Solutions

solution 1: {2 8 14} {4 9 11} {5 6 13}

solution 2: {2 9 13} {4 6 14} {5 8 11}

Thanks

Upvotes: 2

Views: 3968

Answers (1)

LBushkin
LBushkin

Reputation: 131806

Unfortunately the constrained k-subset problem is a hard problem ... and if you want to generate all such k-subsets, you have no choice but to evaluate many possible candidates.

There are a couple of optimizations you can perform to reduce the search space.

Given a domain x constaining integer values, Given a positive integer target M, Given a positive integer k size for the subset,

  1. When x only contains positive integers, and given a upper bound M, remove all items from x larger than or equal to M. These can't possibly be part of the subset.
  2. Similarly, for k > 1, a given M, and x containing positive integers, remove all items from x which are larger than M + min0 + min1 ... minK. Essentially, remove all of the large values which can't possibly be part of the subset since even when selecting small values they will results in a sum in excess of M.
  3. You can also use the even/odd exclusion principle to pare down your search space. For instance, of k is odd and M is even, you know that the sum will either contain three even numbers or two odd and one even. You can use this information to reduce the search space by eliminating candidate values from x that could be part of the sum.
  4. Sort the vector x - this allows you to rapidly exclude values that can't possibly be included in the sum.

Many of these optimizations (other than the even/odd exclusion) are no longer useful/valid when the vector x contains negative values. In this case, you pretty much have to do an exhaustive search.

As Jilles De Wit points out, if X contains negative numbers you could add the absolute value of the smallest value in X to each member of X. This would shift all values back into positive range - making some of the optimizations I describe above possible again. This requires, however, that you are able to accurately represent positive values in the enlarged range. One way to achieve this would be to internally use a wider type (say long instead of int) to perform the subset selection search. If you do this, however, remember to scale the results subsets back down by this same offset when you return your results.

Upvotes: 1

Related Questions