Thanx @DON, was looking for it for a bit of time... I myself wrote
some piece of code though urs is the better one....
On Apr 19, 10:21 am, Don <dondod...@gmail.com> wrote:
> 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.
