@ Adolfo : little more detail about your approach will be helpful.
On Sat, Jan 7, 2012 at 7:07 PM, Adolfo Ccanto <[email protected]> wrote: > this problem is solved in O(n*s), where n is the size of Array and s is > the sum, the aproach is Dynamic Programming. > > > 2012/1/6 saurabh singh <[email protected]> > >> @all Yes it is possible to find the solution using 0/1 knapsack.....The >> approach would be similar as in case of LCS problem when many LCS are >> possible.Though the implementation could be a bit difficult.For each >> subproblem when the choice of dubproblems become equally beneficial start a >> new thread with both the subproblems... >> >> Saurabh Singh >> B.Tech (Computer Science) >> MNNIT >> blog:geekinessthecoolway.blogspot.com >> >> >> >> On Sat, Jan 7, 2012 at 2:01 AM, Don <[email protected]> wrote: >> >>> Given an array A[n], start by sorting the array. >>> Then do something like this: >>> >>> int result[n]; >>> int size=0; >>> >>> void findSubset(int sum, int position=0) >>> { >>> if (sum == 0) output(result, size); >>> for(int i = position; i < n; ++i) >>> { >>> if (A[i] > sum) break; >>> result[size++] = A[i]; >>> findSubset(sum-A[i], i+1); >>> --size; >>> } >>> } >>> >>> Call it like this: findSubset(4); >>> >>> Don >>> >>> On Jan 3, 5:26 am, atul anand <[email protected]> wrote: >>> > There is integer array like {1,2,4,5,6,1,2,4,3,5,7,2,1}. I want to >>> find the >>> > possible combination which will sum to 4. >>> > input : {1,2,4,5,6,1,2,4,3,5,7,2,1} >>> > output : {1,1,2}, {2,2}, {3,1}, {1,2,1}{4}...etc which make the sum as >>> 4 >>> > >>> > any approach better than O(n^2) ??? >>> >>> -- >>> 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. >> > > -- > 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.
