OK. that is the assumption of the problem that this is done in O(n). Perhaps it is imaginary. The Question is : assuming this algorithm and using that, now we want to find the exact members that their sum equals to K, with the best order. Thank you.
On Mar 30, 7:38 pm, "Muntasir Azam Khan" <[EMAIL PROTECTED]> wrote: > On Mar 30, 10:07 pm, "Muntasir Azam Khan" <[EMAIL PROTECTED]> > wrote: > > > > > ----- Original Message ----- > > From: "Mahdi" <[EMAIL PROTECTED]> > > To: "Algorithm Geeks" <[email protected]> > > 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 [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
