To remove duplicate combination in DON code...here is the modified code:- Given an array A[n], start by sorting the array. Then do something like this:
int result[n]; int size=0; int prev=-1; // added 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; if(prev!=A[i]) // added { result[size++] = A[i]; findSubset(sum-A[i], i+1); prev=A[i]; // added --size; } } } Call it like this: findSubset(4); On Sat, Jan 7, 2012 at 10:25 PM, atul anand <atul.87fri...@gmail.com> wrote: > @Don : your algorithm will works but it will print lots of duplicate > combination. > > > > > On Sat, Jan 7, 2012 at 10:00 PM, atul anand <atul.87fri...@gmail.com>wrote: > >> @Don : what would be the complexity of your alogithm?? >> >> >> 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.