@all
Check the link that i have provided above.. It solves the problem
using DP..
On Jan 7, 7:15 pm, atul anand <atul.87fri...@gmail.com> wrote:
> @ Adolfo : little more detail about your approach will be helpful.
>
>
>
>
>
>
>
> On Sat, Jan 7, 2012 at 7:07 PM, Adolfo Ccanto <adol...@gmail.com> 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 <saurab...@gmail.com>
>
> >> @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 <dondod...@gmail.com> 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 <atul.87fri...@gmail.com> 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 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.
--
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.
