和为零——USACO2.3.3

如果n==7,则从0枚举到222222（三进制）

0看做是空格，1看做+，2看做减号-

若果是1 2 3+4+5+6-7，则将其前三个数合成一个数123+4+5-7（方法是使shu[n]=3,for（1->7））

#include<stdio.h>
#include<math.h>
int shu[10];
int fu[10];
int bao[10];

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int i,temp=0,first=0;
        for(i=1;i<=n-1;i++)
        {
            temp+=2*pow(3,i-1);
        }

        int j,max;
        max=temp;
        for(i=0;i<=max;i++)
        {
            temp=i;
            for(j=n-1;j>=1;j--)
            {
                shu[j]=temp%3;
                temp-=shu[j];
                temp/=3;
            }

            int add=1;
            for(j=1;j<=n-1;j++)//不是空的加入
            {
                if(shu[j]!=0)
                {
                    fu[add]=shu[j];
                    add++;
                }
            }

            int shi=add;
            add=1;
            int f,e,k,cha,all;
            shu[n]=3;
            for(j=1;j<=n;j++)
            {
                all=0;
                f=j;
                while(shu[j++]==0);
                j--;

                cha=j-f;
                for(k=f;k<=j;k++)
                {
                    all+=k*pow(10,cha);
                    cha--;
                }
                bao[add]=all;
                add++;
            }

            all=bao[1];
            for(j=2;j<=shi;j++)
            {
                if(fu[j-1]==1)
                    all+=bao[j];
                if(fu[j-1]==2)
                    all-=bao[j];
            }

            if(all==0)
            {
                printf("1");
                for(j=1;j<=n-1;j++)
                {
                    if(shu[j]==1)
                        printf("+");
                    else if(shu[j]==2)
                        printf("-");
                    else if(shu[j]==0)
                        printf(" ");
                    printf("%d",j+1);
                }
                printf("\n");
            }
            
        }
    }
}