CODEWITHSUNDEEP
algorithmsorting
user2052801
user2052801

Reputation: 3

Can it be possible to compute in linear time O(n) or O(nlogn)

I am trying to find an approach in O(n) or O(n log n) to return the output in the following case. If i have a set with n elements and i need to find the minimum set of numbers in the set which adds up to the number given.

For example, A=[0,9,1,2,5,4], If i were given with q=6, then my possible combinations are: (2+4), (1+5) and should return null if no proper subset is found?, This is not an homework question, I just want to learn for good programming approaches.

Upvotes: 0

Views: 80

Answers (1)

argentage
argentage

Reputation: 2778

The general problem is the http://en.wikipedia.org/wiki/Subset_sum_problem.

To the best of our knowledge there are no polynomial-speed algorithms which solve the problem and it is believed that none exist. However, some good approximation methods exist.

Upvotes: 1

Related Questions