子集和数问题

　　子集和数问题是假定有n个不同的正数(通常称为权)，要求找出这些数中所有使得某和数为M的组合。

子集和数问题的递归回溯算法,代码如下：

void SumOfSub(s,k,r) {
//找w(1:n)中和数为M的所有子集。进入此过程时x(1),…,X(k-1)的值已确定。
k-1 n
//s=ΣW(i)X(i)且r=ΣW(j)。W(j)按非递减排列。假定w(1)≤M，ΣW(i)≥M
j=1 j=k
l int M，n；float W[n]；bool X[n]； //M、W[n]、X[n]定义成全局变量
2 float r，s；int k，j；
//生成左子结点。注意，由于Bk-1=true，因此s + w[k]≤M
3 X[k]=1；
4 if(s+w[k]==M) { //子集找到
5 print(X[j],j=1 to k)；}
//由于W(j)＞0，1≤j≤k，所以不存在递归调用
6 else
7 if(s＋W[k]＋W[k+1]<=M) { //Bk=true
8 SumOfSub(s+W[k]，k+1，r-W[k])；}
9 //endif
10 //endif
//生成右孩子和计算 Bk的值 //
11 if((s+r-W[k]>=M) and (s＋w(k＋1)<=M)) { //Bk=true
12 X[k]=0；
13 SumOfSub(s,k+l,r-W[k])；
14 }；//if
15}//SumOfSub

#include <stdio.h>
int M,n;
int w[100];
int x[100];
void SumOfSub(int s, int k, int r)
{
     //s=w[1]*x[1]+...+w[k-1]*x[k-1]
     //r=w[k]+...w[n]
     //w[i]需要按非降次序排列
    int i;
    x[k]=1;
    for(i=1; i<=k; i++)
       printf("%d", x[i]);
    printf("/n");
    if(s+w[k]==M) //子集找到
    {
        printf("ans:");
        for(i=1; i<=k; i++)
            printf("%d", x[i]);
        printf("/n");
    }else if(s+w[k]+w[k+1]<=M)
        SumOfSub(s+w[k], k+1, r-w[k]);

    if(s+r-w[k]>=M && s+w[k+1]<=M)
    {
        x[k]=0;
        SumOfSub(s, k+1, r-w[k]);
    }
}
int main()
{
    int s,k,r;
    n=4;
    w[1]=7;
    w[2]=11;
    w[3]=13;
    w[4]=24;
    M=31;

    s=0;
    k=1;
    r=55;

    SumOfSub(s, k, r);
    getchar();
    return 0;
}