子集和数问题（回溯法）

【问题描述】给定一个n个整数的集合X={x1,x2,…xn}(X中可能包含重复元素)和整数y，找出和等于y的X的子集Y。例如说，如果X={10,30,20,60,40,50}，和y=60,则有4种不同的解，他们分别是{10,20,30},{10,50},{20,40},{60}。
【输入形式】输入的第1行包含两个整数n和y，分别表示集合X的长度和目标整数y。接下来1行包含n个整数(整数之间以空格分割)，表示X中的n个元素。
【输出形式】输出1或0，若存在解，输出1，不存在则输出0。
【样例输入】

6 60

10 30 20 60 40 50
【样例输出】

1

题解：

解向量：
此题的解向量，严格来说，有两种。以题干中的例子$W$={10,30,20,60,40,50}来说明，一种是题干中所给出的变长解{10,20,30}，{10,50}，{20,40}，{60}；另一种就是使用布尔向量表示的定长解$x_1$={1,1,1,0,0,0}，$x_2$={1,0,0,0,0,1}，$x_3$={0,0,1,0,1,0}，$x_4$={0,0,0,1,0,0}，0和1也就表示的是此位置的数选或者不选。本题解采用的是定长解向量。

规范函数：
设$w[i]$为第$W$中的第$i$个数，则有$\sum w[i]\ast x[i]=y$，说人话的话，由于$x[i]$的取值只有0或者1，因此若$x[i]$为0，也就是第$i$个数没有被选中时，$w[i]\ast x[i]$就为0，所以前面的式子的意思就是所有的解必须满足选中的$w[i]$求和等于$y$

其实我们明确了解向量和规范函数之后就可以暴力地写一个深搜了，把所有可能地解都枚举一遍，只要找到满足规范函数的一个解向量就$return$。

bool flag=false;
void dfs(int k, int sum){
	if(k>n){
		return;
	}
	if(sum==y){
		flag=true;
		return;
	}
	//选第k个数的情况
	x[k]=1;
	dfs(k+1,sum+w[k]);
	//不选第k个数的情况
	x[k]=0;
	dfs(k+1,sum);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

虽然这样写，思路很简单，但是时间复杂度高达$2^n$（每个数有2种选择，选或者不选，组合起来总的选择数就为$2^n$），而且做了很多没有必要的搜索，因此，有必要进行剪枝。

• 由于此题中的$w$集合中元素的顺序对我们解决问题不会产生影响，我们首先对输入的$w$数组进行从小到大的排序。
• 我们为dfs函数的参数添加两个形参，$s$表示前$k-1$个数的范围内选中的数的和，$r$表示还未搜索的数之和，显然，$r+s=sum$总是成立的
• 当我们考虑选中第$k$个数的时候，我们预想一下，如果加上第$k+1$个数的话，$s$的值超过了$y$，那么其实我们就没有必要选第$k$个数了，因为继续搜索下去不可能搜索到解。而且我们事先已经排好了序，如果加上$w[k+1]$大于$y$，那加上$w[k+2]$肯定也是大于$y$的，因此只需判断是否满足$s+w[k]+w[k+1]<=y$。
• 当我们考虑不选第$k$个数的时候，我们需要考虑剩余的数之和$r$和目前的$s$加起来能不能达到$y$，如果不能，说明剩下的数根本不够用，也不可能产生解。除此之外，假如剩下的数足够选，这个时候同样需要判断加上$w[k+1]$会不会大于$y$，一旦大于了，就没有搜索下去的必要了。

代码实现：

#include 
#include 
using namespace std;
int n, y, w[1001], sum = 0, x[1001];
set<string> vis;
//子集和数问题

bool flag = false;
void dfs(int k, int s, int r) {
    if (k > n) {
        return;
    }
    x[k] = 1;
    if (s + w[k] == y) {
        flag = true;
        return;
    }
    else {
        if (s + w[k] + w[k + 1] <= y) {
            dfs(k + 1, s + w[k], r - w[k]);
            x[k] = 0;
        }
        if (s - w[k] + r >= y && s + w[k + 1] <= y) {
            x[k] = 0;
            dfs(k + 1, s, r);
        }
    }
}

int main()
{
    cin >> n >> y;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        sum += w[i];
    }
    if (sum >= y) {
        sort(w + 1, w + 1 + n);
        dfs(1, 0, sum);
        if (flag)
            cout << 1;
        else {
            cout << 0;
        }
    }
    else {
        cout << 0;
    }
    return 0;
}
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
48
49
50