Re: [algogeeks] Re: finding all combination
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.
Re: [algogeeks] Re: finding all combination
@ 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.
[algogeeks] Re: finding all combination
@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.
Re: [algogeeks] Re: finding all combination
@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.
[algogeeks] Re: finding all combination
@atul.. So following the above previous posted link.. the time complexity would be 4*n = O(n)... [ just adding it here, because i saw that u went thru the link.. :)] On Jan 7, 9:30 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.
Re: [algogeeks] Re: finding all combination
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.comwrote: @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.
Re: [algogeeks] Re: finding all combination
Sorry for being offtopic but yes if anyone proposes a polynomial time algorithm(which can work for all cases) he is entitled to a prize money of 1 million. http://en.wikipedia.org/wiki/Millennium_Prize_Problems Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sat, Jan 7, 2012 at 11:46 PM, Gene gene.ress...@gmail.com wrote: If you have an O(n^2) algorithm, you will be famous because you will have proven that P=NP. As has been pointed out, this is the subset sum problem, well known to be NP hard. It is only weakly NP hard, though. There is a simple pseudo- polynomial time DP algorithm. Let S(n, k) be a boolean function true iff there is a subset of elements that sum to n using only elements 1,2,...,k. Then S(n,k) = S(n,k-1) or S(n - a[k], k-1) for n,k0. The base cases are S(0,k)=true for k=0 and S(n,0)= false for n0. The intuition here is you either skip usiong the k'th item in the subset or use it. This just tells you whether a subset exists. It's easy to find the subset elements with back pointers in the DP table, which will form a tree rooted at S(n, N) where the array has N elements. Each root-leaf path in the tree will be a valid subset. This algorithm is polynomial in the _size_ of the elements, which is exponential time by the normal definition, but can be useful if data are small. That's why it's called pseudo-polynomial time. On Jan 3, 12:26 pm, 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.
[algogeeks] Re: finding all combination
@atul007: When you mean n^2 solution.. did you mean the DP which actually is 2^n?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/MrOfjqZKk8YJ. 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.
Re: [algogeeks] Re: finding all combination
@shady , prakash : we have to find all combination , not one so could you providelittle more explanation by using 0-1 knapsack. @ sravanreddy001: yeah it should be O(2^n). On Fri, Jan 6, 2012 at 8:07 PM, sravanreddy001 sravanreddy...@gmail.comwrote: @atul007: When you mean n^2 solution.. did you mean the DP which actually is 2^n?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/MrOfjqZKk8YJ. 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.
[algogeeks] Re: finding all combination
@ The following link might help.. http://groups.google.com/group/algogeeks/browse_thread/thread/8a58ea05c96f811b?hl=en# Basicaly if A[N, Wmax] = 1, then find all subsets using backtracking.. where, N = no. of elements, Wmax = 4... On Jan 6, 7:50 pm, atul anand atul.87fri...@gmail.com wrote: @shady , prakash : we have to find all combination , not one so could you providelittle more explanation by using 0-1 knapsack. @ sravanreddy001: yeah it should be O(2^n). On Fri, Jan 6, 2012 at 8:07 PM, sravanreddy001 sravanreddy...@gmail.comwrote: @atul007: When you mean n^2 solution.. did you mean the DP which actually is 2^n?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/MrOfjqZKk8YJ. 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.
Re: [algogeeks] Re: finding all combination
@atul007: the 0-1 knapsack is a special case of subset sum problem, (and.. i don't think its easy to find all the solutions using 0/1 knapsack.. ) @shady: is it possible? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/2xspry_EJxoJ. 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.
[algogeeks] Re: finding all combination
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(i+1, sum-A[i]); --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.
[algogeeks] Re: finding all combination
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.
Re: [algogeeks] Re: finding all combination
@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.
[algogeeks] Re: finding all combination
@atul ,FYI, another naive approach will to generate the all subset of given set , thats the power set , has complexity O(n*2^n) , obviously not better then upper one , but still you can try to figure out the sum problem , you will get some relation to DP. Thanks Shashank Mani Computer Science Birla Institute of Technology,Mesra *http://shashank7s.blogspot.com* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/Di1eSEnE8XQJ. 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.