零的数列 Zero Sum

题目描述

请考虑一个由1到N（N=3, 4, 5 ... 9）的数字组成的递增数列：1 2 3 ... N。 现在请在数列中插入“+”表示加，或者“-”表示减，“ ”表示空白(例如1-2 3就等于1-23)，来将每一对数字组合在一起（请不要在第一个数字前插入符号）。 计算该表达式的结果并判断其值是否为0。 请你写一个程序找出所有产生和为零的长度为N的数列。

输入输出格式

输入格式：

单独的一行表示整数N (3 <= N <= 9)。

输出格式：

按照ASCII码的顺序，输出所有在每对数字间插入“+”, “-”, 或 “ ”后能得到结果为零的数列。

输入输出样例

输入样例#1：

7

输出样例#1：

1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7

说明

翻译来自NOCOW

USACO 2.3

【题解】

我的思路是先无序生成，接着排序。

    /*
    ID:luojiny1
    LANG:C++
    TASK:zerosum
    */
    #include<cstdio>
    #include<string>
    #include<algorithm>
    using namespace std;
    string s[50];//答案
    int N,m=0,ans=0, num[10],connect[10];// ans为答案个数，num表示目前生成的数字序列，connect是每个数字之间的符号
    void dfs(int step,int sum)
    {
    if(step>=N+1){
        if(sum==0)
        {
            for(int i=0;i<m;i++)
        {
        if(i)
        s[ans]+=(connect[i]==1?'+':'-');
        char a=num[i]/10+'0',b=num[i]%10+'0';
    if(num[i]>10)
            s[ans]=s[ans]+a+' '+b;
        else
        s[ans]+=b;
        }
        ans++;
        }
        return ;
    }
    num[m]=0;
    for(int i=step;i<=step+1&&i<=N;i++)//很明显最多能连续两个数，否则会大于100。
    {
        num[m]=num[m]*10+i;
        connect[m++]=1;
        dfs(i+1,sum+num[m-1]);
        connect[m-1]=0;
        if(step!=1)
        dfs(i+1,sum-num[m-1]);
        m--;
    }
    }


    int main()
    {
    //	freopen("zerosum.in","r",stdin);
    //freopen("zerosum.out","w",stdout);
    scanf("%d",&N);
    dfs(1,0);
    sort(s,s+ans);
    for(int i=0;i<ans;i++)printf("%s\n",s[i].c_str());
    return 0;
    }