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 <[email protected]>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
> <[email protected]> wrote:
> > @Navneet: does the set contains negative elements also?
> >
> > On Mon, Jun 20, 2011 at 12:26 PM, pacific :-) <[email protected]>
> wrote:
> >>
> >> @vaibhav : Please note that more than two numbers can sum upto k.
> >>
> >> On Mon, Jun 20, 2011 at 12:21 PM, vaibhav shukla <
> [email protected]>
> >> 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 <[email protected]
> >
> >>> 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 . <
> [email protected]>
> >>>> 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 <
> [email protected]>
> >>>>> 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 [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.
> >>>>
> >>>>
> >>>>
> >>>> --
> >>>> --Navneet
> >>>>
> >>>> --
> >>>> 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.
> >>>
> >>>
> >>>
> >>> --
> >>> 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 [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.
> >>
> >>
> >>
> >> --
> >> 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 [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.
> >
>
>
>
> --
> --Navneet
>
> --
> 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.
>
>
--
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 [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.
