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;
}