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

输入格式

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

输出格式

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

输入样例

1
2
4 31
11 13 24 7

输出样例

1
2
11 13 7 
24 7

解题思路

定义的a[ ]数组，是用来存放输入的数据

定义的x[ ]数组，每一个元素的值是0或1，用来判断当前节点是在子集树中是向左走还是向右走。

通过题目分析可知，本题中应当使用 子集树 作为解空间，使用tw记录当前整数和，使用rw记录余下的整数的和。

扩展节点的约束条件：tw+a[i] <= c i 表示子集树的层数

如果把当前节点加入到当前的整数和中小于等于目标c，那么表示当前节点需要加进来，用x[i]=1表示加进来了，也表示向左走。加进来之后tw=tw+a[i],rw=rw-a[i]

扩展节点的限界函数：tw+rw-a[i]>=c||tw+a[i]>=c

如果a[i]加不进来，那么x[i]=0，代表向右走。

tw+rw-a[i]>=c 表示不加a[i]当前的tw和那些没有被访问的数的和是不是大于等于c,如果不是这样，也就没有向右走的必要了在，再怎么加也加不到目标值c了。一旦决定向右走了，当前的a[i]，也就不作数了，必须执行rw=rw-a[i]。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
//含有剪枝
int a[999];//用于存储S的正整数集合
bool x[999];//用于记录各分支的结果情况
int tw=0,rw;//tw：当前整数和，rw：余下的整数和
bool flag=false;//记录是否有解
int n,c;
 
void backtrack(int i) {
	if(i>n||flag==true)
		return ;
	if(tw==c) {
		for(int j=0; j<i; j++)
			if(x[j]==1)
				cout<<a[j]<<" ";
		flag=true;
		return ;
	}
	if(tw+a[i]<=c) {//进入左子树,剪枝
		x[i]=1;
		tw=tw+a[i];
		rw=rw-a[i];
		backtrack(i+1);
		tw=tw-a[i];
		rw=rw+a[i];
	}
	if(tw+rw-a[i]>=c) {//进入右子树，剪枝
		x[i]=0;
		rw=rw-a[i];
		backtrack(i+1);
		rw=rw+a[i];
	}
	return ;
}
 
int main() {
	cin>>n>>c;
	for(int i=0; i<n; i++) {
		cin>>a[i];
		rw=rw+a[i];
	}
	backtrack(0);
	if(flag==false)
		cout<<"No Solution!\n";
	return 0;
}