Here is the program with better documentation and a fix for the case when sum is zero.
// Number of elements to select from const int setSize = 20; // Unique integers to select from int set[setSize] = { 5,9,1,3,4,2,6,7,11,10,13,15,19,22,25,31,33,37,39,40}; // Desired sum of subset const int sum = 165; // Stores the current subset int rec[setSize]; int recCount = 0; int subset=0; // Find a subset of set which adds to sum void search(int *set, int setSize, int sum) { // If we found a subset, print it if ((sum == 0) && recCount) { printf("Subset %d: {%d", ++subset,rec[0]); for(int i = 1; i < recCount; ++i) printf(",%d", rec[i]); printf("}\n"); } else if (sum > 0) { // Consider elements of the set to add to the subset for(int i = 0; i < setSize; ++i) { // Include set[i] in the subset rec[recCount++] = set[i]; // Look for remaining elements which add to sum search(set, i, sum-set[i]); // Back out set[i] to try subsets without set[i] --recCount; } } } int main(int argc, char* argv[]) { search(set, setSize, sum); printf("Found %d subsets\n", subset); return 0; } On Apr 18, 11:58 pm, kamlesh yadav <kamleshlu2...@gmail.com> wrote: > @Don thanks, nice one, but can u give a little bit of explanation. > > > > On Mon, Apr 18, 2011 at 10:14 PM, Don <dondod...@gmail.com> wrote: > > const int setSize = 20; > > int set[setSize] = > > { 5,9,1,3,4,2,6,7,11,10,13,15,19,22,25,31,33,37,39,40}; > > const int sum = 150; > > > int rec[setSize]; > > int recCount = 0; > > int subset=0; > > > void search(int *set, int setSize, int sum) > > { > > int i; > > if (sum == 0) > > { > > printf("Subset %d: {%d", ++subset,rec[0]); > > for(i = 1; i < recCount; ++i) > > printf(",%d", rec[i]); > > printf("}\n"); > > } > > else if (sum > 0) > > { > > for(i = 0; i < setSize; ++i) > > { > > rec[recCount++] = set[i]; > > search(set, i, sum-set[i]); > > --recCount; > > } > > } > > } > > > int main(int argc, char* argv[]) > > { > > search(set, setSize, sum); > > > return 0; > > } > > > On Apr 18, 6:16 am, kamlesh yadav <kamleshlu2...@gmail.com> wrote: > >> given an array of elements (all elements are unique ) , given a sum > >> s find all the subsets having sum s. > > >> for ex array {5,9,1,3,4,2,6,7,11,10} > > >> sum is 10 > > >> possible subsets are {10}, {6,4} ,{7,3} {5,3,2} > >> {6,3,1} etc. there can be many more. > >> also find the total number of these subsets > > > -- > > 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 > > athttp://groups.google.com/group/algogeeks?hl=en. > > -- > Kamlesh Kumar Yadav > MCA Department of Computer Science > Delhi University -- 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.