This is the subset sum problem which is NP,. The DP is as follows,
M[i,j] = 1 , if a subset of first i elements has a sum = j. else 0, The recurrence is, M[i,j] = max(M[i-1,j] , M[i-1,j-Ai]) where Ai is the ith element. You can maintain back pointers to keep track of previous elements so that the solution can be reconstructed from the DP. Once this matrix is populated till sum=k, Then, the column corresponding to sum=k, gives the answer. complexity o(nk). On Jun 20, 6:38 pm, Harshal <hc4...@gmail.com> wrote: > The problem is NP. Complexity using DP will be O(nk), where n is number of > elements and k is required sum. > > S[0]=true; //choose no element > S[1...k] = false; > for each number i in your input > for s = k downto i > if ( S[s - i] == true ) > S[s] = true; > > S[s] = true indicates a sum of i can be obtained from a subset of the set. > To get the elements, we can make S[s] contain the list of numbers that > contain the sum. > On Mon, Jun 20, 2011 at 6:53 PM, Navneet Gupta <navneetn...@gmail.com>wrote: > > > > > > > > > > > Ideally, yes it can. Though i would be happy even if someone gives a > > good answer for non-negative values. > > > On Mon, Jun 20, 2011 at 6:28 PM, Akshata Sharma > > <akshatasharm...@gmail.com> wrote: > > > @Navneet: does the set contains negative elements also? > > > > On Mon, Jun 20, 2011 at 12:26 PM, pacific :-) <pacific4...@gmail.com> > > wrote: > > > >> @vaibhav : Please note that more than two numbers can sum upto k. > > > >> On Mon, Jun 20, 2011 at 12:21 PM, vaibhav shukla < > > vaibhav200...@gmail.com> > > >> wrote: > > > >>> sort the array using merge sort : order nlogn > > >>> take the first element,subtract it with 'k' , then search the result > > >>> using binary search in rest of the array : order nlogn > > >>> hence u get two elements which sum up to K in order nlogn > > > >>> On Mon, Jun 20, 2011 at 12:14 PM, Navneet Gupta <navneetn...@gmail.com > > > >>> wrote: > > > >>>> Right, in the worst case, complexity with be O(2^N). > > >>>> So what are the possible optimizations here? Would building > > pre-computed > > >>>> data structures with intermediate sum values help in finding such > > pairs in > > >>>> less complexity? I think then we can apply dynamic programming to find > > such > > >>>> pairs. > > > >>>> On Mon, Jun 20, 2011 at 12:09 PM, oppilas . < > > jatka.oppimi...@gmail.com> > > >>>> wrote: > > > >>>>> I think its a NP problem. The solution complexity can go up O(2^N) in > > >>>>> worst case. > > > >>>>> On Mon, Jun 20, 2011 at 11:55 AM, Navneet Gupta < > > navneetn...@gmail.com> > > >>>>> wrote: > > > >>>>>> Given a set of integers , find a set of numbers such that they sum > > to > > >>>>>> a given number k . > > >>>>>> Notice the set of numbers can have 2 or more than 2 numbers. > > > >>>>>> --Navneet > > > >>>>>> -- > > >>>>>> 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 > > >>>>>> 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 algogeeks@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. > > > >>>> -- > > >>>> --Navneet > > > >>>> -- > > >>>> 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 > > >>>> algogeeks+unsubscr...@googlegroups.com. > > >>>> For more options, visit this group at > > >>>>http://groups.google.com/group/algogeeks?hl=en. > > > >>> -- > > >>> best wishes!! > > >>> Vaibhav Shukla > > >>> DU-MCA > > > >>> -- > > >>> 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 > > >>> algogeeks+unsubscr...@googlegroups.com. > > >>> For more options, visit this group at > > >>>http://groups.google.com/group/algogeeks?hl=en. > > > >> -- > > >> regards, > > >> chinna. > > > >> -- > > >> 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 > > >> 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 algogeeks@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. > > > -- > > --Navneet > > > -- > > 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 > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Harshal Choudhary, > Final Year B.Tech CSE, > NIT Surathkal, Karnataka, India. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
