Problem 36: Zero Sum
Zero Sum

Consider the sequence of digits from 1 through N (where N=9) in increasing order: 1 2 3 ... N.

Now insert either a `+' for addition or a `-' for subtraction or a ` ' [blank] to run the digits together between each pair of digits (not in front of the first digit). Calculate the result that of the expression and see if you get zero.

Write a program that will find all sequences of length N that produce a zero sum.

PROGRAM NAME: zerosum

INPUT FORMAT

A single line with the integer N (3 <= N <= 9).

SAMPLE INPUT (file zerosum.in) 

7

OUTPUT FORMAT

In ASCII order, show each sequence that can create 0 sum with a `+', `-', or ` ' between each pair of numbers.

SAMPLE OUTPUT (file zerosum.out)

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

题意:
在任意两个数字之间插入加号，减号，或是空格，空格表示将被隔开的两个数并起来组成一个数。
代码：


/*
LANG: C
TASK: zerosum
*/
#include<stdio.h>
int n, T[10];
char ch[20], S[300000][20], p[10];
int cmp(const void * a, const void * b)
{
    return strcmp( (char *)a, (char *)b );
}
int k = 0;
int Is()
{
    int i, j, t = 2 * n - 1, num, sum;
    for (i = 0, j = 0, num = 0; i < t; i++)
    {
        if (ch[i] == '+' || ch[i] == '-')
        {
            T[j] = num;
            p[j++] = ch[i];
            num = 0;
        }
        else if (ch[i] == ' ')
        {
            continue;
        }
        else
        {
            num = num * 10 + ch[i] - '0';
        }
    }
    T[j] = num;
    sum = T[0];
    for (i = 0; i < j; i++)
    {
        if (p[i] == '+')
        {
            sum += T[i+1];
        }
        else
        {
            sum -= T[i+1];
        }
    }
    if (sum == 0)
    {
        
        strcpy(S[k++], ch);
    }
}        
void Dfs(int depth)
{
    int t = depth * 2;
    if (depth == n)
    {
        Is();
        return;        
    }    
    ch[t - 1] = '+';
    Dfs(depth + 1);
    ch[t - 1] = '-';
    Dfs(depth + 1);
    ch[t - 1] = ' ';
    Dfs(depth + 1);
}  
int main()
{
    freopen("zerosum.in", "r", stdin);
    freopen("zerosum.out", "w", stdout);
    int len, i;
    scanf("%d", &n);
    len = 2 * n;
    for (i = 1; i <= n; i++)
    {
        ch[(i-1) * 2] = i + '0';
    }    
    ch[len] = 0;
    Dfs(1);
    qsort(S, k, sizeof(char) * 20, cmp);
    for (i = 0; i < k; i++)
    {
        puts(S[i]);
    }
    fclose(stdin);
    fclose(stdout);
    //system("pause");
    return 0;
}