# Poj Solution 1950

```http://poj.org/problem?id=1950

//* @author:alpc12
import java.io.*;
import java.util.*;
import java.math.*;

public class Main {

char[] opa = { '+', '-', '.' };
char[] op;
int cnt;
int n;
int rec[] = {88, 162, 197, 437, 1350 };

void print() {
cnt++;
if(cnt > 20) return;
int i;
for(i = 1; i <= n; ++i) {
System.out.print(i);
if(i != n){
System.out.print(" " + op[i] + " ");
}
}
System.out.println("");
}

void search(int depth, long lastnum, char lastop, long tot) {
if(cnt > 20) return;
if(depth == n) {
if(lastop == '+')
tot += lastnum;
else tot -= lastnum;

if(tot == 0)
print();
return;
}
for(char c : opa) {
char curop = lastop;
long curtot = tot;
if(c == '+') {
op[depth] = c;
if(lastop == '+') tot += lastnum;
else tot -= lastnum;
lastop = c;
search(depth+1, depth+1, lastop, tot);
} else if(c == '-') {
op[depth] = c;
if(lastop == '+') tot += lastnum;
else tot -= lastnum;
lastop = c;
search(depth+1, depth+1, lastop, tot);
} else if(c == '.') {
op[depth] = c;
String s = "" + lastnum;
s += (depth+1);
if(s.length() > 9) continue;
long x = Long.parseLong(s);
search(depth+1, x, lastop, tot);
}
tot = curtot;
lastop = curop;
}
}

void run() {
Scanner cin = new Scanner(System.in);
n = cin.nextInt();
op = new char[n];
cnt = 0;
search(1, 1, '+', 0);
if(n < 11)
System.out.println(cnt);
else
System.out.println(rec[n-10-1]);
}

public static void main(String[] args) {
new Main().run();

}

}
```
This entry was posted in poj. Bookmark the permalink.