Wrote the code for same.
#include<iostream> using namespace std; int max(int a,int b) { if(a>b) return a; else return b; } int main() { int n,k; cout<<"\nEnter the count of numbers :"; cin>>n; //Set of Elements cout<<"\nEnter the elements :"; int *A; A = new int[n]; for(int i = 0; i<n; i++) cin>>A[i]; //Input Sum Value cout<<"\nEnter the value of k :"; cin>>k; //Matrix for holding boolean values for subproblems (max subproblems upto nk) int **M; M = (int **)new int[n]; for(int i=0; i<n; i++) M[i] = new int[k+1]; //Populate all the values to false for(int i=0; i<n; i++) for(int j=0; j<=k; j++) M[i][j] = 0; for(int i=0; i<n; i++) M[i][0] = true; for(int i=1; i<n; i++) for(int j=0; j<=k; j++) if(j-A[i]>=0) { M[i][j] = max(M[i-1][j], M[i-1][j-A[i]]); } if(M[n-1][k] == 1) cout<<"\nPossible Subset present"; else cout<<"\nPossible Subset not present"; cin.get(); return 0; } On Fri, Jun 24, 2011 at 11:42 PM, ross <jagadish1...@gmail.com> wrote: > This is the subset sum problem which is NP,. > > The DP is as follows, > > M[i,j] = 1 , if a subset of first i elements has a sum = j. > else 0, > The recurrence is, > M[i,j] = max(M[i-1,j] , M[i-1,j-Ai]) where Ai is the ith element. > > You can maintain back pointers to keep track of previous elements so > that > the solution can be reconstructed from the DP. > > Once this matrix is populated till sum=k, Then, the column > corresponding to sum=k, gives > the answer. complexity o(nk). > > > > On Jun 20, 6:38 pm, Harshal <hc4...@gmail.com> wrote: >> 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 <navneetn...@gmail.com>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 >> > <akshatasharm...@gmail.com> wrote: >> > > @Navneet: does the set contains negative elements also? >> >> > > On Mon, Jun 20, 2011 at 12:26 PM, pacific :-) <pacific4...@gmail.com> >> > wrote: >> >> > >> @vaibhav : Please note that more than two numbers can sum upto k. >> >> > >> On Mon, Jun 20, 2011 at 12:21 PM, vaibhav shukla < >> > vaibhav200...@gmail.com> >> > >> 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 <navneetn...@gmail.com >> >> > >>> 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 . < >> > jatka.oppimi...@gmail.com> >> > >>>> 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 < >> > navneetn...@gmail.com> >> > >>>>> 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 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. >> >> > >>>> -- >> > >>>> --Navneet >> >> > >>>> -- >> > >>>> 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. >> >> > >>> -- >> > >>> 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 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. >> >> > >> -- >> > >> 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 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. >> >> > -- >> > --Navneet >> >> > -- >> > 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. >> >> -- >> 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 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. > > -- --Navneet -- 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.