hdu 1258 Sum It Up 搜索

#include<bits/stdc++.h>
using namespace std;

int cmp(int a,int b)
{
    return a>b;
}
int flag,t,n,a[20],use[20];

void dfs(int sum,int now)
{
    int i;
    if(sum==t)
    {
        flag=1;
        int st=0;
        for(i=0;i<n;i++)
        {
            if(use[i]==1)
            {
                if(st==0) st++;
                else printf("+");
                printf("%d",a[i]);
            }
        }
        printf("
");
        return;
    }
    if(now==n) return ;
    for(i=now;i<n;i++)
    {
        if(a[i]==a[i-1]&&use[i-1]==0) continue;
        if(a[i]+sum>t) continue;
        use[i]=1;
        dfs(sum+a[i],i+1);
        use[i]=0;
    }
}

int main()
{
    int i;
    while(~scanf("%d%d",&t,&n))
    {
        if(t==0&&n==0) break;
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n,cmp);
        printf("Sums of %d:
",t);
        flag=0;
        for(i=0;i<n;i++)
        {
            memset(use,0,sizeof(use));
            if(i&&a[i-1]==a[i]) continue;
            use[i]=1;
            dfs(a[i],i+1);
        }
        if(!flag)
            printf("NONE
");
    }
    return 0;
}