问题标题: 怎么做子集和问题

使用搜索与回溯，还要剪枝。

核心程序

bool search(int t,int p)
{
    int i;
    bool f;
    if(sum==c)
    {
        print(t-1);
        return true;
    }
    if(sum>c || t>n) return false;
    if(sum+sd[p]<c||sum+md[p]>c) return false;
    for(int i=p; i<=n; i++)
    {
        sum+=a[i];
        k++;
        ans[t]=a[i];
        f=search(t+1,i+1);
        sum-=a[i];
        ans[t]=0;
        if(f)return true;
    }
    return false;
}

sd数组求法

for(int i=n-1; i>=1; i--)
    {
        sd[i]=sd[i+1]+a[i];
    }

md数组求法

for(int i=n-1; i>=1; i--)
    {
        md[i]=min(a[i],md[i+1]);
    }