@ Subhranshu : Your approach will fail for a case let X = {-1,4,2,3} and your sum is 5. You will get nearest element 4, but there is no 1 in the set. A DP solution will be like this :
Let a[i][j] be the 1 if using the first i elements we can get sum of j, and 0 otherwise. Initialise a[0][j] = 0, a[i][0] = 1; Now a[i][j] = a[i-1][j] | a[i-1][ j - X[i] ], where X[i] is ith element of set X. On Wed, Mar 30, 2011 at 12:35 PM, hammett <hamm...@gmail.com> wrote: > I'd try a tabular approach. Check dynamic programming. Samples like > LCS may give you a click. > > > On Tue, Mar 29, 2011 at 11:46 PM, Subhransu > <subhransu.panigr...@gmail.com> wrote: > > set of integers in an array X that the sum equals a given number N > > > > Eg. X = {-1, -3, 5, 13, 2, 24, 9, 3, 3} > > > > Lets say the number 5 which can be formed in the following manner 5= 2 + > 3 > > (the values from array). If there is no match it has to return > > invalid numbers. > > > > We also have to see the complexity of the solution. > > > > I thought of one approach but not sure if there is more approach where > the > > complexity will be minimal. > > Lets say sort the array and now take number and find the closest number > for > > that. > > Then in a recursion manner search for another( Lets say number '5', it > > search the list and found closest match > > will be 3. Then recursively search for 3 now where closest match is 2) > > > > Any algo with better complexity will be appreciated. > > > > Subhransu Panigrahi > > > > Email: subhransu.panigr...@gmail.com > > > > -- > > 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. > > > > > > -- > Cheers, > hammett > http://hammett.castleproject.org/ > > -- > 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.