Scribd
Upload
13 views3 pages

C/C++ Subset Sum Problem Solution

The document contains a C/C++ program designed to find subsets of a given set of positive integers that sum to a specified positive integer. It includes functions for inputting the set and the target sum, as well as a recursive function to explore possible subsets. The program checks for the feasibility of finding such subsets and prints them if they exist.

Uploaded by

snehahanjgimath
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
13 views3 pages

C/C++ Subset Sum Problem Solution

The document contains a C/C++ program designed to find subsets of a given set of positive integers that sum to a specified positive integer. It includes functions for inputting the set and the target sum, as well as a recursive function to explore possible subsets. The program checks for the feasibility of finding such subsets and prints them if they exist.

Uploaded by

snehahanjgimath
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

Program 8 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>

// #include<conio.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:

You might also like