An interesting variation of the subset sum problem was presented to me by a friend from work:Given a set S of positive integers, of size n, and integers a and K, is there a subset R (of the set S) that contains exactly a elements, whose sum is equal to K?He claims that this can be done with time complexity O(nKa), I was unable to come up with a dynamic programming algorithm that achieved this running time. Can it be done?
Interesting variation to the subset sum problem
cc.complexity theory;ds.algorithms;dynamic algorithms
Doesn't the usual (pseudo-polynomial time) dynamic programming algorithm solve this, with a minor tweak?The usual approach is to have a table with flags there is a subset of $x_1,x_2,...,x_i$ with sum $s$ for all $i = 1, 2, ..., n$ and $s = 0, 1, ..., K$.The minor modification is to have a table with flags there is a subset of $x_1,x_2,...,x_i$ with $c$ elements and sum $s$ for all $i = 1, 2, ..., n$, $c = 1, 2, ..., a$, and $s = 0, 1, ..., K$.