Shady , how do you valide the case that a, b, c, d are diferente, i.e a=x[i] , b=x[j], i!=j ?
2012/1/1 Lucifer <sourabhd2...@gmail.com> > @ SAMM.. > > The following might work, but would need verification.. > > Below solution is for a generic no. of elements. > In your case its 4. > Lets represent 4 by R. > > Lets take a 2-dim array named A, to store the intermediate values.. > > Now, X ( A[i, j] , p ) basically means whether given the first 'i' > elements is it possible to make a sum of 'j' using only 'p' elements > from the first 'i' elements. > > The recurrence equation would be: > X( A[i, j], p ) = X( A[i - 1, j], p ) || X( A[i - 1, j - A[i]] , p > - 1) ; > > The value of X( A[i,j], p) will be reflected by A[i,j] > > Value of 0 means not possible and a value of 1 means possible. > > The base conditions would be: > X( A[i, 0] , 0) = 1; > X( A[i, 0] , > 0) = 0; > X( A[i, j], 0) = 0; > > If X( A[N, K], 4) = 1, then we can backtrack and get the required nos. > > // I think we can make 'p' part of array A as follows: > // A[N][K][1] .. the last index [1] can be used to store the count.. > > O(N*K) time and O(N*K) space.. > > ------------------------------------------------ > > Let me know if it helps... > > ------------------------------------------- > > > On Jan 1, 10:53 pm, shady <sinv...@gmail.com> wrote: > > O((n^2)*logn) > > if problem is a+b+c+d=e > > find all combinations of e-a-b O(N^2) as e is constant > > similarly find for c+d also O(N^2) > > > > then sort then so O((N^2)*logn) > > and do a binary search for each value of e-a-b in c+d array.... > > > > > > > > > > > > > > > > On Sun, Jan 1, 2012 at 11:08 PM, SAMMM <somnath.nit...@gmail.com> wrote: > > > HAPPY NEW YEAR to all Geeks !!! > > > > > Given an array of size N and a integer Num(K) . Need to find the > > > combination of four no's in the array whose sum is equal to Num(K). > > > Needed a solution whose complexity is less than O(n^3) . > > > > > -- > > > 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.
