3

Following from these question Subset sum problem and Sum-subset with a fixed subset size I was wondering what the general algorithm for solving a subset sum problem, where we are forced to use EXACTLY k integers, k <= n.

Evgeny Kluev mentioned that he would go for using optimal for k = 4 and after that use brute force approach for k- 4 and optimal for the rest. Anyone could enlight what he means by a brute force approach here combined with optimal k=4 algo?

Perhaps someone knows a better, general solution?

Community
  • 1
  • 1
Bober02
  • 15,034
  • 31
  • 92
  • 178
  • Do you need to apply the algorithm multiple times? or just on one set of numbers? If it's just one set of numbers I suggest you manually play around with the numbers to see what patterns, sparsity etc they have – Rusty Rob Mar 23 '12 at 12:27
  • Well, I need to fin it only once, but it is still non-trvial. You need to ensure that you take exactly k elements from the array, hence my question – Bober02 Mar 23 '12 at 13:35

1 Answers1

6

The original dynamic programming algorithm applies, with a slight extension - in addition to remembering partial sums, you also need to remember number of ints used to get the sums.

In the original algorithm, assuming the target sum is M and there are n integers, you fill a boolean n x M array A, where A[i,m] is true iff sum m can be achieved by picking (any number of) from first i+1 ints (assuming indexing from 0).

You can extend it to a three dimensional array nxMxk, which has a similar property - A[i,m,l] is true iff, sum m can be achieved by picking exactly l from first i+1 ints.

Assuming the ints are in array j[0..n-1]:

The recursive relation is pretty similar - the field A[0,j[0],1] is true (you pick j[0], getting sum j[0] with 1 int (duh)), other fields in A[0,*,*] are false and deriving fields in A[i+1,*,*] from A[i,*,*] is also similar to the original algorithm: A[i+1,m,l] is true if A[i,m,l]is true (if you can pick m from first i ints, then obviously you can pick m from first i+1 ints) or if A[i, m - j[i+1], l-1] is true (if you pick j[i+1] then you increase the sum by j[i+1] and the number of ints by 1).

If k is small then obviously it makes sense to skip all of the above part and just iterate over all combinations of k ints and checking their sums. k<=4 indeed seems like a sensible threshold.

Rafał Dowgird
  • 43,216
  • 11
  • 77
  • 90
  • I wonder how the above compare to this: http://stackoverflow.com/questions/8916539/sum-subset-with-a-fixed-subset-size/8926458#comment12539828_8926458 – Bober02 Mar 23 '12 at 22:43