This s similar to the problem https://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.
