#include"fstream"
#include"iostream"
using namespace std;
#define N 1000   //數組的長度
int x[N];        //判斷數組
int num;         //元素的個數

void subset_sum(int subset,int p[N],int s,int k,int sum){//前k-1個x[i]的值以定
	int i,j;
	x[k]=1;          //將第k個元素的取上   
	if(s+p[k]==subset){
		for(j=k+1;j<=num;j++){
			x[j]=0;  //將k以后的位置的值全置零
		}
		ofstream ofile;
		ofile.open("F:\\測試數據\\回溯法\\子集和問題\\out_subsum5.out");
		for(i=1;i<=num;i++)
			if(x[i]!=0)ofile<<p[i]<<" "; //根據判斷數組將所選的元素輸出的文件
		ofile<<endl;
		ofile.close();
		cout<<"任務完成！"<<endl;
		exit (0);                      //找到其中的一個解后即退出程序
	}
	if (s+p[k]+p[k+1]<=subset){        //如果當前取值的總和再加上后面的一項仍沒有超過子集總和
		subset_sum(subset,p,s+p[k],k+1,sum-p[k]);//繼續遞歸調用
	}
	if(s+sum-p[k]>=subset&&s+p[k+1]<=subset){
		x[k]=0;                        //將當前的第k個元素去掉
		subset_sum(subset,p,s,k+1,sum-p[k]);    //向后取一項后繼續遞歸調用
	}
}


int main(){
	
	int subset;      //子集的和
	int p[N];        //讀入的數組
	int i;
	int sum=0;       //數組元素的總和大小
	int s=0,k=1;     //s為目前取的數的總和大小，k為元素的序號

	ifstream ifile;
	ofstream ofile;
	ifile.open("F:\\測試數據\\回溯法\\子集和問題\\test\\subsum5.in");
	ifile>>num;      //讀入數組元素的個數
	cout<<"num="<<num<<endl;
	ifile>>subset;   //讀入子集的總和
	cout<<"subset="<<subset<<endl;
	cout<<"讀入數組...";
	for(i=1;i<=num;i++){      //從下標為1的位置開始將元素裝入p數組
		ifile>>p[i];
		sum=sum+p[i];         //計算數組元素的總和
	}
	cout<<endl;
	subset_sum(subset,p,s,k,sum);  //子集回溯函數
	return 0;
}