Computer Science: 5th sem ADA Lab Program 10

Analysis and Design of Algorithms Lab.

Question 10.

//Find a subset of a given set s = {s1,s2,....sn} of n positive integers whose sum is equal to a given positive integer d.
//(they cannot repeat more than once)

#include <iostream>
#include <conio.h>

using namespace std;

void sumOfSubset(int curSum,int i,int d,int *arr,int *vis,int n)
//curSum=current sum untill this point
//i= the next number to add
//d is the integer to compare
//arr is the original array input in ascending order
//vis is the array to keep track of the visted index in the orginal array. 1=visited,0=not visited
//n is the size of the input

{
if(curSum==d)
{
//print the answer
for(int i=0;i<n;i++)
if(vis[i]>0)
cout<<arr[i]<<" ";
cout<<"\n";
}
if(i<n)
{

if(curSum<d)
{
if(curSum+arr[i]<=d)
{
vis[i]+=1;
sumOfSubset(curSum+arr[i],i+1,d,arr,vis,n);
vis[i]=0;
sumOfSubset(curSum,i+1,d,arr,vis,n);
}

else
{
vis[i]=0;
sumOfSubset(curSum,i+1,d,arr,vis,n);
}

}
}
}

void main()
{
cout<<"Enter the value of d:";int d;cin>>d;
cout<<"Enter the size of the array:";int n;cin>>n;
cout<<"Enter the Array:\n";
int *arr=new int[n];
int *vis=new int[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
vis[i]=0;
}
cout<<"\nAny subsets=\n";

sumOfSubset(0,0,d,arr,vis,n);

getch();
}