程序填空题：求子集和问题（回溯法）
给定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
```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
