USACO-T032: Zero Sum

/*
ID: mickyta1
TASK: zerosum
LANG: C++
*/

#include <bits/stdc++.h>
using namespace std;

string str;
int n;
char opr[4] = " +-";

void BFcheck(){
    stack<int> stk;
    stk.push(1);
    for(int i = 2; i <= n; ++i){
        char c = str[i - 2];
        if(c == ' '){
            stk.top() = (10 * stk.top() + i);
        } else if(c == '+' || c == '-'){
            int s = stk.top(); stk.pop();
            if(stk.empty()){
                stk.push(s);
                stk.push(c);
            } else {
                int o = stk.top(); stk.pop();
                int f = stk.top(); stk.pop();
                int ans = o == '+' ? f + s : f - s;
                stk.push(ans);
                stk.push(c);
            }
            stk.push(i);
        }
    }
    if(stk.size() > 1){
        int s = stk.top(); stk.pop();
        int o = stk.top(); stk.pop();
        int f = stk.top(); stk.pop();
        int ans = o == '+' ? f + s : f - s;
        stk.push(ans);
    }
    if(stk.top() == 0){
        cout << '1';
        for(int i = 2; i <= n; ++i){
            cout << str[i - 2] << i;
        }
        cout << '\n';
    }
}

void recur(int i, int n){
    if(i == n){
        BFcheck();
        return;
    }
    for(int j = 0; j < 3; ++j){
        str.push_back(opr[j]);
        recur(i + 1, n);
        str.pop_back();
    }
}

int main(){
    freopen("zerosum.in", "r", stdin);
    freopen("zerosum.out", "w", stdout);

    scanf("%d", &n);
    recur(0, n - 1);

    fclose(stdin);
    fclose(stdout);
    return 0;
}