题目描述： Subset Sum

Tags: 回溯

子集和问题的一个实例为〈 S,t 〉。其中，S={x1 ，x2 ，…， xn }是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得x1+x2+…+xk=S, 其中x1,x2…xk属于集合S1。 对于给定的正整数的集合S和正整数c，编程计算S 的一个子集S1，使得x1+x2+…+xk=S, 其中x1,x2…xk属于集合S1。

输入

第1 行有2 个正整数n 和c，n 表示S 的大小，c是子集和的目标值。接下来的1 行中，有n 个正整数，表示集合S 中的元素。

输出

子集和问题的解。当问题无解时，输出“No Solution!”。

样例输入

5 10
2 2 6 5 4

样例输出

2 2 6

思路：DFS，找一个子集树就可以了，但是总是PE。。。。。这个就很头痛。。。。。

// subset sum.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

#include
#include
#include
using namespace std;

const int MAX = ;
int n, c, sign, arr[MAX], vis[MAX], sum[MAX];

void print()
{
for (int i = ; i<n; i++)
if (vis[i]) cout << arr[i] << " ";
cout << endl;
}

//搜索的位置，目前的和
void DFS(int pos, int cur)
{
//cout << "pos:" << pos << "\tcur:" << cur << endl;
if (sign) return; //找到一组就可以直接结束搜索过程
if (cur == c)
{
sign = ; print();
return;
}

 //加个特殊判断，cur+余下<c 不可能凑够c  
 if (pos >= n || cur > c || cur + sum\[n-\] - sum\[pos-\] < c ) return;

 vis\[pos\] = ;//选择  
 DFS(pos + , cur + arr\[pos\]);

 vis\[pos\] = ;//不选择  
 DFS(pos + , cur);

}

int main()
{
while (cin >> n >> c)
{
sign = ;
memset(vis, , sizeof(vis));
memset(sum, , sizeof(sum));

     for (int i = ; i < n; i++)  
     {  
         cin >> arr\[i\];  
         sum\[i\] = sum\[i-\] + arr\[i\]; //减枝！！判断剩下的所有的数字是否能够合成c  
     }  
     if (sum\[n-\] < c)//很重要的剪枝！！如果所有的数加起来都小于c，那么不可能有解。。之前有三组TLE，加了这一步竟然给蒙过了。。  
     {  
         //cout << "sum\[n - 1\]:"<<sum\[n - 1\] << endl;  
         cout << "No Solution!";  
     }  
     else  
     {  
         DFS(, );  
         if (sign == ) cout << "No Solution!"<<endl;  
     }

 }

 return ;  

}