子集和问题

子集和问题可描述如下：给定n个正整数W=(w1, w2, …, wn)和正整数M，要求寻找这样一个子集I⊆{1, 2, 3, ..., n},使得∑wi=M,i∈I[1]。举个例子对子集和问题做一个通俗的解释：集合W=(1, 2, 3, 4, 5)，给定一个正整数M=5，是否存在W的一个子集I，使得子集I中的元素相加等于M，这个例子显然存在子集I=(2, 3)。

　　问题定义：正整数集合S=(w1, w2, w3, …，wn)，给定正整数W，s[i, j]中的i表示S的一个子集，j表示子集i的和。如果S的某个集合i元素之和j=M，即问题有解。

　　举例：S=(7, 34, 4, 12, 5, 3)，W=6，是否存在S的一个子集，它的元素之和等于W。

思路：先搜索回溯，如果该子集各元素的和大于w，回溯；等于就直接输出。

注意：只要求输出第一个满足条件的子集，所以找到后不必继续搜索。

#include
using namespace std;
int a[10000],ans[10000],sum[10000],n,c;
void print(int n)
{
	for (int i=1;ic) return ;
	if (tot==c) print(k);
	if (tot+sum[x]0;i--)
		sum[i]=sum[i+1]+a[i];
	if (sum[1]>=c) search(1,0,1);	
	puts("No Solution!");
	return 0;
}