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?
It can be done if k and a are small enough, so that we can declare an array
bool found[a][k]
You would iterate over each value in S and iterate over every state in the found array to obtain a new state.
Say, for the indexes of a=1 and k = 7, and the current value from S being 7,
if found[1][7] is true, then you can also be sure that found[2][14] is also true.
When the iteration ends, all you need to do is check that [a][k] is true or not.