A DFS solution would be fast enough to pass the tests. We have just N-1 places to put signs where N is the number of digits we can use. This yields that the time complexity of our algorithms is O(3^(N-1)) where N can be maximum 9. We will generate every possible expression and then evaluate it. If it sums to zero, then we just print it. In order to get in in ASCII order, we will first use the empty sign, then the + sign and then the – sign.

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;
ifstream in;
ofstream out;
int n;
vector<int> numbers;
char signs[10];
int calcSum() {
int sum = numbers[0];
for (int i = 1; i < numbers.size(); ++i) {
if (signs[i-1]=='+') {
sum+=numbers[i];
} else {
sum-=numbers[i];
}
}
return sum;
}
void printSolution() {
for (int i = 0; i < numbers.size(); ++i) {
int tmp = numbers[i];
string c;
while (tmp!=0) {
c.insert(0,1,(char)(tmp%10 + '0'));
if (tmp>10) c.insert(0,1,' ');
tmp/=10;
}
out << c;
if (i+1!=numbers.size()) out << signs[i];
}
out << endl;
}
void dfs(int curNumber, int curSign) {
if (curNumber == n+1) {
int sum = calcSum();
if (sum==0) {
printSolution();
}
return;
}
numbers[numbers.size()-1] = numbers[numbers.size()-1]*10+curNumber;
dfs(curNumber+1,curSign);
numbers[numbers.size()-1] = (numbers[numbers.size()-1]-curNumber)/10;
signs[curSign] = '+';
numbers.push_back(curNumber);
dfs(curNumber+1,curSign+1);
signs[curSign] = '-';
dfs(curNumber+1,curSign+1);
numbers.pop_back();
}
int main() {
in.open("zerosum.in");
in >> n;
in.close();
out.open("zerosum.out");
numbers.push_back(1);
dfs(2,0);
out.close();
}

Another idea (not implemented): It is fairly obvious that we cannot have more than 2 empty signs since the integer would get too big and we cannot get a zero sum. We could generate every possible number (1,2,3,4 … 12,23,34 … 89). Keep an array dp[2000]. If dp[x] is equal to one, then we can generate the value X. We will always add an offset to the sum. That’s why we have to create such a big array. We will also keep a vector array (vector from[2000]) to keep the solutions. After we have calculated all the possible sums using dynamic programming, we will just use the from array to print all the solutions. What’s the time complexity? We have N numbers and a sum from -1000 to +1000 (+offset). For every number we will have to either add it, subtract it or append it to the current number in the dp array. The time complexity is O(C*N) where C is the maximum size of the array. As you have probably noticed, this solution is very similar to the 1-0 knapsack problem.