@ 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.
