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 <[email protected]> wrote:
> @Don thanks, nice one, but can u give a little bit of explanation.
>
>
>
> On Mon, Apr 18, 2011 at 10:14 PM, Don <[email protected]> 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 <[email protected]> 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 [email protected].
> > To unsubscribe from this group, send email to
> > [email protected].
> > 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
