We did :-) Dynamic programming seems as the best way to approach this kind of problem.
On Wed, Mar 30, 2011 at 12:56 AM, Subhransu <subhransu.panigr...@gmail.com> wrote: > For this X = {-1,4,2,3} > Nearest will be 4 then remain is 1 but the there is no 1 so again in > recursion nearest number is 2 then it search for suitable number where the > sum is zero so 3 is not suitable then it will pick the next closest number > to 2 which is one and make it (5= 4 + 2 -1 ) > > I just propose one approach you guys also can think a better one. > > Subhransu Panigrahi > > Mobile: +91-9840931538 > > Email: subhransu.panigr...@gmail.com > > > On Wed, Mar 30, 2011 at 12:55 PM, Saikat Debnath <crazysai...@gmail.com> > wrote: >> >> @ 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. > > -- > 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.