Sum of subset problem solve in CPP

This is an algorithm. Here goes the coding of sum of subset problem in C++. Do it!! 😀

#include iostream.h
#include stdlib.h
#include time.h
#include math.h
#include conio.h

//plz insert the tags of header libraries by your own

int a[50],b[50];
int x[50];
int n,m,total;

void merg(int L,int M,int H)
{
	int i=L, j=L, k=M+1;
	while((i<=M)&&(k<=H))
	{
		if(a[i]M)
	{
		for(int t=k;t<=H;t++,j++)
			b[j]=a[t];
	}
	else
	{
		for(int t=i;t<=M;t++,j++)
			b[j]=a[t];
	}
	for(int f=L;f<=H;f++)
		a[f]=b[f];

}
void MS(int low,int high)
{
	if(low<high)
	{
		int mid=int((low+high)/2);
		MS(low,mid);
		MS(mid+1,high);
		merg(low,mid,high);
	}
}
SumOfSub(int s,int k,int r)
{	 
	x[k]=1;
	if(s+a[k]==m)
	{
		for(int i=1;i<=n;i++)
			cout<<' '<<x[i];
		cout<<endl;
	}
	else if(s+a[k]+a[k+1]=m)&&(s+a[k+1]<=m))
	{
		x[k]=0;
		SumOfSub(s,k+1,r-a[k]);
	}
}
void main()
{
	cout<>n;
	cout<<"random data choosen:\n";
//	randomize();

	for(int i=1;i<=n;i++)
	{
		a[i]=rand()%100	;
		total=total+a[i];
		cout<<" "<<a[i]<<endl;
	}
	MS(1,n);

	cout<<"\nsorted data:\n";
	for(i=1;i<=n;i++)
	{
		cout<<" "<<a[i]<<endl;
	}
	
	while(1)
	{
	cout<>m;
	if(m==0)
		break;
	else
		SumOfSub(0,1,total);
	}
	//	getch();
}
  • Also try with ( coded by SVN ):
    #include
    #include
    using namespace std;
    
    
    // this is the class
    class SumOfSub
    {
    	int sumToFind;
    	int *array;
    	int *resultArray;
    	int remainSum;
    	int totalSum;
    	int dataNo;
    public:
    	SumOfSub(int noOfData);
    	void sumOfSubSet(int tSum,int index,int rSum);
    	void getData();
    	void sortData();
    	void printData(int *data);
    	void printData();
    	int getTotalSum();
    };
    
    /*void SumOfSub::printData()
    {
    	for(int i=0;i<dataNo;i++)
    	{
    		cout<<resultArray[i]<<" ";//=((int)(tempTimeGetter%100000)*rand())%100;
    	}
    	cout<<endl;
    }*/
    
    int SumOfSub::getTotalSum()
    {
    	int totVal=0;
    	for(int i=0;i<dataNo;i++)
    		totVal+=array[i];
    	//totVal-=pSum;
    	//pSum=array[--i];
    	return totVal;
    }
    
    void SumOfSub::printData(int *data)
    {
    	for(int i=0;i<dataNo;i++)
    	{
    		cout<<data[i]<<" ";//=((int)(tempTimeGetter%100000)*rand())%100;
    	}
    	cout<<endl;
    }
    
    void SumOfSub::sortData()
    {
    	for(int i=0;i<dataNo-1;i++)
    		for(int j=i+1;jarray[j])
    				swap(array[i],array[j]);
    	this->printData(array);
    }
    
    void SumOfSub::getData()
    {
    	time_t tempTimeGetter;
    	for(int i=0;iprintData(array);
    }
    
    void SumOfSub::sumOfSubSet(int tSum,int index,int rSum)
    {
    	resultArray[index]=1;
    	if (tSum+ array[index]==sumToFind)
    	{
    		for(int i=0;i<=index;i++)
    			cout<<resultArray[i]<<" ";
    		cout<<endl;
    	}
    	else if (tSum+array[index]+array[index+1]sumOfSubSet(tSum+array[index],index+1,rSum-array[index]);
    	if (tSum+rSum-array[index]>=sumToFind && tSum+array[index+1]sumOfSubSet(tSum,index+1,rSum-array[index]);
    	}
    }
    
    SumOfSub::SumOfSub(int noOfData)
    {
    	try
    	{
    		array=new int [noOfData];
    		resultArray=new int[noOfData];
    
    	}
    	catch(bad_alloc xa)
    	{
    		return;
    	}
    	dataNo=noOfData;
    	this->getData();
    	cout<>sumToFind;
    }
    
    int main()
    {
    	int pSum=0;
    	SumOfSub SOS(5);
    	SOS.sortData();
    	//for(int i=0;i<10;i++)
    		
    		SOS.sumOfSubSet(0,0,SOS.getTotalSum());
    	
    //	SOS.printData();
    	return 0;
    }
    
    
  • Leave a Reply

    Please log in using one of these methods to post your comment:

    WordPress.com Logo

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

    Google photo

    You are commenting using your Google 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 )

    Connecting to %s