子集和数问题是一个集合里面的数字从中取出一个或多个数字相加可以等于所要求和的数字。
这个问题是用回溯方法来实现的，先上代码再进行讲解。
#include
const int m = 30;//所要最后求和的值
void printresult(int *w, int *x,int n)
{
for(int i = 1; i <= n; i++)
{
if(x[i])
{
printf("%d ",w[i]);
}
}
printf("\n");
}
void SumOfSub(int s, int k, int r, int *w, int *x)
{
x[k] = 1;
if((w[k] + s) == m)
{
//打印结果
printresult(w, x, k);
}else{
if((s + w[k] + w[k+1]) <= m)
{
SumOfSub(s+w[k], k+1, r-w[k], w, x);
}
}
if((s + r - w[k]) >= m && (s + w[k+1]) <= m)
{
x[k] = 0;
SumOfSub(s, k+1, r-w[k], w, x);
}
}
int main()
{
printf("所要求的和为%d\n",m);
int w[7] = {0, 5, 10, 12, 13, 15, 18};//数组元素
int x[7] = {0, 0, 0, 0, 0, 0, 0};//判断是否选中了 这里设置为bool变量的会要好一点
SumOfSub(0, 1, 73, w, x);
return 0;
}
这里我在主函数中定义了两个数组，一个是存放集合中的数组元素的w[7] 一个是与数组元素长度一样的数组x[7]是用来存放数组元素相对应的位置是否存放了如果存放了就设置为1否则设置为0这里设为bool变量的会更好一点。
有两个函数一个是用来输出的函数printresult输出结果的函数目的是判断x[7]这个数组为1的位置来输出w[7]相对应的数这样就可以把我们所得到的这个集合输出出来。
另一个是比较重要的函数SumOfSub这个函数是来进行判断子集和数的一个函数。在这个函数当中我们需要传进去参量分别为 现在的和 现在找到的位置 剩余元素的和 w这个数组 x这个数组
在SumOfSub这个函数中我们把当前输入进去的k这个位置先设为1然后我们判断这个判断是这样的我们不仅需要加k这个位置的元素我们也要加上k+1这个位置的元素。为什么呢，我们这个数组是按照大小顺序排列好的如果我们加上这个元素没有达到预计值那么我们还需要加另外的元素最小的就是他后面的元素，所以我们直接这么判断就可以了这样会更高效。经过这样的比较我们发现如果可以的话我们可以设置为1即加入进去否则我们就设置为0表示无法加进去。如果发现现在的和与我们想要的数字相等那我们就可以调用输出函数进行输出。