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 standard input/output header file
#define MAX 10 // Define a constant MAX with value 10
int s[MAX], x[MAX], d; // Declare three arrays: s and x of size MAX and an integer variable d
/* Function to find the subset of elements that sum up to a given value It uses three parameters:
p for the current sum of the subset.
k for the current index.
r for the remaining sum of the elements not yet considered.*/
void sumofsub(int p, int k, int r)
{
int i;
x[k] = 1; // Include the k-th element in the subset
// If the sum of the subset is equal to the desired sum (d)
if ((p + s[k]) == d)
{
// Print the subset
for (i = 1; i <= k; i++)
if (x[i] == 1)
printf("%d ", s[i]);
printf("\n");
}
else
{
// If including the next element does not exceed the desired sum
if (p + s[k] + s[k+1] <= d)
sumofsub(p + s[k], k + 1, r - s[k]); // Recur with the next element included in the subset
}
// If the remaining sum after excluding the current element is still >= d and including the next element does not exceed the desired sum
if ((p + r - s[k] >= d) && (p + s[k+1] <= d))
{
x[k] = 0; // Exclude the k-th element from the subset
sumofsub(p, k + 1, r - s[k]); // Recur with the next element excluded from the subset
}
}
int main()
{
int i, n, sum = 0;
printf("\nEnter the n value:");
scanf("%d", &n); // Input the number of elements in the set
printf("\nEnter the set in increasing order:");
for (i = 1; i <= n; i++)
scanf("%d", &s[i]); // Input the elements of the set
printf("\nEnter the max subset value:");
scanf("%d", &d); // Input the desired sum value (d)
for (i = 1; i <= n; i++)
sum = sum + s[i]; // Calculate the total sum of the set
// If the total sum is less than the desired sum or the smallest element is greater than the desired sum
if (sum < d || s[1] > d)
printf("\nNo subset possible");
else
sumofsub(0, 1, sum); // Call the sumofsub function to find the subset
return 0;
}
OUTPUT:
Enter the n value:5
Enter the set in increasing order:1 2 5 6 8
Enter the max subset value:9
1 2 6
1 8