@ 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 <[email protected]> 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
> <[email protected]> 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: [email protected]
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected].
> > 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
