It is known to me that element 'k' is less than the sum of all elements in the set/array.
I know the solution if 'k' can be formed adding any two numbers or three numbers in the set. There are well known algorithms fr that. But how to generalize this solution if the key information i.e. numbers of elements which adds up to 'k' is unknown.
Should I check for combinations of each length (Brute force algorithm with exponential time complexity). Is there an optimum way to do so?
For example: $$Array = [1, 2, 3, 4, 6, 7] $$and $$key = 18$$ Now we have
$$7 + 6 + 4 + 1 = key$$
So if I make a function $validate()$ which outputs "True" if k can be formed by adding any number of elements in Array and "False" otherwise. In above example:
$$validate(Array, 18) = True$$
Is it possible to construct this function in polynomial time complexity?
Best Answer
Like M. Vinay says, this problem is a (very slight modification of) the subset-sum problem, which is known to be NP-complete. So far, nobody knows whether or not a polynomial-time algorithm exists which can detect if $k$ can be formed by adding some subset of the array, although most (but not all) researchers in the field believe it is impossible.