Scribd
Upload
9 views2 pages

Subset Program

The document presents a C/C++ program that finds subsets of a given set of positive integers whose sum equals a specified integer. It includes a recursive function to explore possible combinations and outputs valid subsets. The program also checks for conditions where no subset is possible based on the input values.

Uploaded by

nidhi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views2 pages

Subset Program

The document presents a C/C++ program that finds subsets of a given set of positive integers whose sum equals a specified integer. It includes a recursive function to explore possible combinations and outputs valid subsets. The program also checks for conditions where no subset is possible based on the input values.

Uploaded by

nidhi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Design and implement C/C++ Program to find a subset of a given set S = {sl ,

s2,.....,sn} of n positive integers whose sum is equal to a given positive integer


d.

#include<stdio.h>
#define MAX 10
int s[MAX],x[MAX],d;
void sumofsub(int p,int k,int r)
{
int i;
x[k]=1;
if((p+s[k])==d)
{
for(i=1;i<=k;i++)
if(x[i]==1)
printf("%d ",s[i]);
printf("\n");
}
else
if(p+s[k]+s[k+1]<=d)
sumofsub(p+s[k],k+1,r-s[k]);
if((p+r-s[k]>=d) && (p+s[k+1]<=d))
{
x[k]=0;
sumofsub(p,k+1,r-s[k]);
}
}

int main()
{
int i,n,sum=0;
printf("\nEnter the n value:");
scanf("%d",&n);
printf("\nEnter the set in increasing order:");
for(i=1;i<=n;i++)
scanf("%d",&s[i]);
printf("\nEnter the max subset value:");
scanf("%d",&d);
for(i=1;i<=n;i++)
sum=sum+s[i];
if(sum<d || s[1]>d)
printf("\nNo subset possible");
else
sumofsub(0,1,sum);
return 0;
}

Output:

adminpc@adminpc-ThinkCentre-neo-50t-Gen-3:~$ gedit subset.c


adminpc@adminpc-ThinkCentre-neo-50t-Gen-3:~$ gcc subset.c
adminpc@adminpc-ThinkCentre-neo-50t-Gen-3:~$ ./a.out

Enter the n value:5

Enter the set in increasing order:1 2 5 6 8

Enter the max subset value:9


126
18

adminpc@adminpc-ThinkCentre-neo-50t-Gen-3:~$ ./a.out

Enter the n value:5

Enter the set in increasing order:1 3 5 6 7

Enter the max subset value:12


156
57
adminpc@adminpc-ThinkCentre-neo-50t-Gen-3:~$

You might also like