On Mar 30, 10:07 pm, "Muntasir Azam Khan" <[EMAIL PROTECTED]> wrote: > ----- Original Message ----- > From: "Mahdi" <[EMAIL PROTECTED]> > To: "Algorithm Geeks" <algogeeks@googlegroups.com> > Sent: Friday, March 30, 2007 1:27 PM > Subject: [algogeeks] Sum of subsets > > > We have set named S. We assume we have an algorithm that specifies if > > there is a subset in S that sum of it's elements equals to K in O(n) > > and returns TRUE or FALSE. The question is : > > How can we find the elements of this subset? What is the best solution > > with minimum order? > > Thanks. > > The best I can come up with is a O(n^2) solution. To me this looks like a > variation of the 0-1 knapsack problem. Could you please elaborate on how you > are checking in O(n)? > > Muntasir
Just a *small* correction to my earlier post. This problem is actually NP-complete. My O(n^2) solution works only if all the members of the set are positive integers. Muntasir --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
