Let there be n elements v1, v2, v3 .. vn
Let S(i,k) mean - Sum k exists in a subset of {v1, v2, v3, ... vi}
At any given time, if solution has not yet been found then :
S(i,k) = S(i-1,k-vi) + vi or no solution exists
We need to find S(n,k)
So in a systematic fashion, solve S(1,1), S(1,2), S(1,3) ... S(1,k) ,
S(2,1), S(2,2), S(2,3), S(2,4) .. S(2,k) , ... S(n,1), S(n,2) ..
S(n,k)
On Wed, Mar 30, 2011 at 2:46 AM, 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.
>
--
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.
