Sum of Subsets

#include<stdio.h>

void sumofsub(int s,int k,int r);
int x[20],w[20],n,m;

void main()
{
    int i,r=0;
    printf("Enter  number of elements ");
    scanf("%d",&n);
    printf("Enter elements ");
    for(i=0;i<n;i++)
    {
        scanf("%d",&w[i]);
        r=r+w[i];
    }
    printf("Enter sum to be computed ");
    scanf("%d",&m);
    printf("\nSubsets whose sum is are as follows\n");
    sumofsub(0,0,r);
}

void sumofsub(int s,int k,int r)
{
    int i;
    x[k]=1;
    if(s+w[k]==m)
    {
        printf("\nElements of set are ");
        for(i=0;i<=k;i++)
            if(x[i]==1)
                printf("%d\t",w[i]);
            printf("\n");
    }
    else if((s+w[k]+w[k+1])<=m)
        sumofsub(s+w[k],k+1,r-w[k]);
    if((s+r-w[k]>=m)&&(s+w[k+1]<=m))
    {
        x[k]=0;
        sumofsub(s,k+1,r-w[k]);
    }
}

/*Output
Enter number of elements 6
Enter elements 5 10 12 13 15 18
Enter sum to be computed 30

Subsets whose sum is are as follows

Elements of set are 5 10 15

Elements of set are 5 12 13

Elements of set are 12 18
*/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s