http://en.wikipedia.org/wiki/Subset_sum_problem
On Dec 25, 10:52 pm, radha krishnan <radhakrishnance...@gmail.com> 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 > > <punnu.gino...@gmail.com> wrote: > > sorry i forgot to attach.... here it is > > > On Sat, Dec 25, 2010 at 10:34 PM, Puneet Ginoria <punnu.gino...@gmail.com> > > 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++ <avpostni...@gmail.com> 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 algoge...@googlegroups.com. > >>> To unsubscribe from this group, send email to > >>> algogeeks+unsubscr...@googlegroups.com. > >>> 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 algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
