程序填空题：求子集和问题（回溯法）

给定n个不同的正整数集合w=（w1，w2，…，wn）和一个正数W，要求找出w的子集s，使该子集中所有元素的和为W。

```c++
#include 
#include 

#define MAXN 20						//最多整数个数

int n,W;
int w[MAXN]={0};				//存放所有整数,不用下标0的元素
void dispasolution(int x[])			//输出一个解
{	int i;
	for (i=1;i<=n;i++)
		if (x[i]==1)
			printf("%d ",w[i]);
	printf("\n");
}
void dfs(int tw,int rw,int x[],int i) //求解子集和
{	//tw为考虑第i个整数时选取的整数和，rw为剩下的整数和
	if (i>n)						//找到一个叶子结点
	{	if ()					//找到一个满足条件的解,输出它
			dispasolution(x);
	}
	else							//尚未找完所有物品
	{
		if ()				//左孩子结点剪枝：选取满足条件的整数w[i]
		{	x[i]=1;					//选取第i个整数
			dfs();
		}
		if ()				//右孩子结点剪枝：剪除不可能存在解的结点
		{	x[i]=0;					//不选取第i个整数,回溯
			dfs();
		}
	}
}

int main()
{   cin>>n>>W;
    for(int i=1;i<=n;i++)
	  cin>>w[i]; 
	int x[MAXN];					//存放一个解向量
	int rw=0;
	for (int j=1;j<=n;j++)			//求所有整数和rw
		rw+=w[j];
	dfs(0,rw,x,1);				//i从1开始
	return 0;
}

```

### 输入格式:

第一行输入n和W，第二行依次输入n个数。

### 输出格式:

每行输出一个符合要求的子集。

### 输入样例1:

```in
4 31
11 13 24 7
```

### 输出样例1:

```out
11 13 7 
24 7   
```





答案：
第1空：tw==W    

第2空：tw+w[i]<=W    

第3空：tw+w[i],rw-w[i],x,i+1    

第4空：tw+rw>W    

第5空：tw,rw-w[i],x,i+1