[USACO] 2-3-3 Zero Sum

/*
ID: 551100k1
LANG: C++
TASK: zerosum
*/
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
vector<string> vec;
bool check(string s){
    int i,ans=0,add=0;
    char c='+';
    for(i=0;i<s.length();i++){
        if(s[i]<='9' && s[i]>='0') add=add*10+s[i]-'0';
        else if(s[i]!=' '){
            if(c=='+') ans+=add;
            if(c=='-') ans-=add;
            add=0;
            c=s[i];
        }
    }
    if(c=='+') ans+=add;
    if(c=='-') ans-=add;
    if(ans) return 0;
    return 1;
}
void dfs(string s,int v){
    if(v==n){
        if(check(s))
            vec.push_back(s);
        return;
    }
    char c=v+1+'0';
    dfs(s+"+"+c,v+1);
    dfs(s+"-"+c,v+1);
    dfs(s+" "+c,v+1);
}
int main(){
    freopen("zerosum.in","r",stdin);
    freopen("zerosum.out","w",stdout);
    int i;
    scanf("%d",&n);
    dfs("1",1);
    sort(vec.begin(),vec.end());
    for(i=0;i<vec.size();i++)
        puts(vec[i].c_str());
}