Interesting variation to the subset sum problem

1
votes

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?

2
algorithmcomplexity-theorydynamic-programmingnp-hard
This is not off-topic, but you may get better answers on cstheory.stackexchange.com. – Björn Pollex
Is there any restriction on the range of numbers? – Shamim Hafiz - MSFT
@Gunner, I think we can assume positive numbers (will edit) @Space_C0wb0y, Thanks! – ntsue

2 Answers

3
votes

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.

3
votes

Let S = {s1,\ldots,sn}

Let P(j,K,a) be true iff it is possible to find a elements in s1,\ldots,sj that sum up to K.

Then P(j,K,a) = P(j-1, K-sj, a-1) OR P(j, K, a) (either sj is needed or it is not needed).

The algorithm then consists of filling out 3-D table of dimension n by K+1 by a+1. Each entry takes constant time to fill, hence the time (and space) complexity is O(nKa)