CODEWITHSUNDEEP
algorithmsubsetsubset-sum
Shaurya Chaudhuri
Shaurya Chaudhuri

Reputation: 3842

Sum of a number with any k elements in Array

Design an algorithm that, given a set S of n integers and another integer x, determines whether or not there exist k (n>k>2) elements in S whose sum is exactly x. Please give the running time of your algorithm

I have been preparing for an interview, and i have come across this algorithm. I have solved problems where k has been specified in the problem. like 2 or 3. But i cannot find an answer where i might solve for any k that might exist. I have tried solving it using dynamic programming but didn't get results. Can anyone help me on this.

Upvotes: 0

Views: 926

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726479

You can make an int array cnt of size x, then go through the set, and mark reachable points. All elements of cnt are set to -1 initially except element zero, which is set to zero.

Repeat the same process for each element si of S: for each element of cnt at position i that is non-negative, check element cnt[i+si] (if it's within the bounds of the array). If it is, set it to cnt[si+i] = max(cnt[i]+1, cnt[si+i]).

Once you go through all elements of S, check cnt[x]. If it is set to two or more, then there exists a combination of two or more elements in S adding up to x.

This algorithm is pseudo-polynomial, with running time O(x*|S|)

Upvotes: 3

Related Questions