5_1_2.cpp

子集和问题（递归回溯）

#include<stdio.h>
#define MMM 20

int n;
int c;
int nc=0;
int find=0;
int A[MMM];
int flag[MMM];
void Backtrack(int i);

void main()
{
	int i;
	FILE *fp1,*fp2;
	if((fp1=fopen("input.txt","r"))==NULL)
	{
		printf("file cannot be opened\n");
		//exit(1);
	}
	fscanf(fp1,"%d %d",&n,&c);
	for(i=0;i<n;i++)
		fscanf(fp1,"%d",&A[i]);
	if((fp2=fopen("output.txt","w"))==NULL)
	{
		printf("file cannot be opened\n");
		//exit(1);
	}
	void Backtrack(int k);
	Backtrack(0);
	if(find)
	{
		for(i=0;i<n;i++)
			if(flag[i]==1)
				fprintf(fp2," %d",A[i]);
	}
	else 
		fprintf(fp2,"No Solution");
}


void Backtrack(int k)
{

	if(nc==c)
	{
		find=1;
		return;
	}	
	if(k>=n)
		return;
	if(!find)
	{         
		if(nc+A[k]<=c)
		{
			flag[k]=1;
			nc=nc+A[k];
			Backtrack(k+1);		
			nc=nc-A[k];	
		}
	}
	if(!find)
	{
		flag[k]=0;
		Backtrack(k+1);
	}

}