soj1030组合树回溯.cpp

一些ACM题目的解答,主要是soj和poj的

#include<stdio.h>
#include<string.h>

int num[13];
int x[13];
int sum,n;
int cw;
int result[1000][13];
int count;

void backtrack(int t)
{
    if(t>n)
    {
        if(cw==sum)
        {
            int i;
            for(i=1;i<t;i++)
            {
                result[count][i]=x[i];
            }
            count++;
        }
    }
    else
    {
        if(cw+num[t]<=sum)
        {
            cw+=num[t];
            x[t]=1;
            backtrack(t+1);
            cw-=num[t];
        }
        x[t]=0;
        backtrack(t+1);
    }
}

int main(void)
{
    while(scanf("%d%d",&sum,&n)==2&&(sum||n))
    {
        int i;
        cw=0;
        count=0;
        for(i=1;i<=n;i++)
            scanf("%d",&num[i]);
        backtrack(1);
        
        int j;
        for(i=0;i<count;i++)
        {
            int k=1;
            for(j=1;j<=n;j++)
            {
                if(result[i][j]==1)
                {
                    result[i][k++]=num[j];
                }
            }
            result[i][0]=k-1;
        }
        printf("Sums of %d:\n",sum);
        bool none=true;
        for(i=0;i<count;i++)
        {
            bool flag=true;
            for(j=0;j<i;j++)
            {
                if(result[i][0]==result[j][0])
                {
                    int k;
                    bool icon=true;
                    for(k=1;k<=result[i][0];k++)
                    {
                        if(result[i][k]!=result[j][k])
                        {
                            icon=false;
                        }
                    }
                    if(icon)
                    {
                        flag=false;
                        break;
                    }
                }
            }
            if(flag)
            {
                printf("%d",result[i][1]);
                int p;
                for(p=2;p<=result[i][0];p++)
                {
                    printf("+%d",result[i][p]);
                }
                puts("");
                none=false;
            }
        }
        if(none)
        {
            printf("NONE\n");
        }
    }
    return 0;
}