窮舉每一種可能,然後計算求值,輸出和爲0的解(其實很多地方可以優化,鑑於這道題數據規模很小n<=9,沒有優化也全過了)

關鍵在於表達式求值,只有加減和空格,所以很容易求值

/*
ID: cmykrgb1
PROG: zerosum
LANG: C++
*/

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

FILE *fi,*fo;
int n;

int ev(char *s)
{
    int thr, opt, sum;
    char *p;
    opt=1;
    thr=sum=0;
    for(p=s; *p; p++) 
    {
        switch(*p)
        {
        case '+':
        case '-':
            sum+=opt*thr;
            thr=0;
            opt=(*p=='+')?1:-1;
            break;
        case ' ':
            break;
        default:
            thr=thr*10+*p-'0';
        }
    }
    }
    sum+=opt*thr;
    return !sum;
}

void search(char *s, int k)
{
    char *p;
    if(k == n-1) 
    {
        if(ev(s))
            fprintf(fo, "%sn", s);
        return;
    }
    for(p=" +-";*p; p++) 
    {
        s[2*k+1]=*p;
        search(s,k+1);
    }
}


int main(void)
{
    int i;
    char str[20];
    fi=fopen("zerosum.in", "r");
    fo=fopen("zerosum.out", "w");
    fscanf(fi, "%d", &n);
    fclose(fi);
    strcpy(str, "1 2 3 4 5 6 7 8 9");
    str[2*n-1]=0;
    search(str, 0);
    return 0;
}