On what basis we will divide the array. (Eg 1. Sort and divide them on positive negative )
On Dec 25, 10:52 pm, radha krishnan <[email protected]> wrote: > This s similar to the problemhttps://www.spoj.pl/problems/SUBSUMS/ > we have to split the array into 2 arrays > say A,B > generate all subsets of each array(both A and B) and another > array(A1,B1) to store the sum of each subset > now take each element of A1 and binarysearch B1 to achieve this sum > assume k=2^(n/2) > overall complexity is (2*(2^(n/2)) + 2*(k(lgk)) +k lgk) > 2^(n/2) for each subset so 2*(2^(n/2)) > k(lg k) -- sorting so 2*(k lg k) > k(lgk)--binary search > > On Sat, Dec 25, 2010 at 10:38 PM, Puneet Ginoria > > > > > > > > <[email protected]> wrote: > > sorry i forgot to attach.... here it is > > > On Sat, Dec 25, 2010 at 10:34 PM, Puneet Ginoria <[email protected]> > > wrote: > > >> This attachment contains the code for the above program in SML language > >> and it uses lambda calculus. > > >> On Sat, Dec 25, 2010 at 9:18 PM, juver++ <[email protected]> wrote: > > >>> What you need to get for the answer - amount of such subsets or display > >>> them? > >>> First problem can be solved using DP. > >>> Second - brute force. > > >>> -- > >>> 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?hl=en. > > > -- > > 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?hl=en. -- 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?hl=en.
