This is a explanation of this problem from USACO's training website. I have converted it to markdown. Please do not just copy code; you will not learn anything; at least type it out and understand so you can do it yourself in the future!

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.

### 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
``````

Java

C++

Pascal

## ANALYSIS

Russ Cox

We can use a simple recursive depth first search to generate all the possible strings to be had by putting in a space, plus, or minus sign between each number.

Once we’ve generated each string, we evaluate it as an arithmetic sum and see if we get zero. If so, we print the string.

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

FILE *fout;
int n;

/* evaluate the string s as arithmetic and return the sum */
int
eval(char *s)
{
int term, sign, sum;
char *p;

sign = 1;
term = 0;
sum = 0;
for(p=s; *p; p++) {
switch(*p){
case '+':
case '-':
sum += sign*term;
term = 0;
sign = *p == '+' ? 1 : -1;
break;
case ' ':
break;
default:    /* digit */
term = term*10 + *p-'0';
}
}
sum += sign*term;
return sum;
}

/*
* Insert + - or space after each number, and then
* test to see if we get zero.  The first k numbers have
* already been taken care of.
*/
void
search(char *s, int k)
{
char *p;

if(k == n-1) {
if(eval(s) == 0)
fprintf(fout, "%s\n", s);
return;
}

for(p=" +-"; *p; p++) {
s[2*k+1] = *p;
search(s, k+1);
}
}

void
main(void)
{
FILE *fin;
int i;
char str[30];

fin = fopen("zerosum.in", "r");
fout = fopen("zerosum.out", "w");
assert(fin != NULL && fout != NULL);

fscanf(fin, "%d", &n);

strcpy(str, "1 2 3 4 5 6 7 8 9");
str[2*n-1] = '\0';    /* chop string to only have first n numbers */

search(str, 0);

exit(0);
}
``````