USACO 2.3 Zero Sum

Brutal force DFS search.

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>

using namespace std;

int N;
vector<char> ops = {'+', '-', ' '};
vector<char> s;
vector<vector<char>> res;

void dfs(int i) {
    if (i == N) {
        int sum = 0, cur = 1, sign = 1;
        for (int i = 2; i <= N; ++i) {
            char op = s[i - 2];
            if (op == ' ') {
                cur = cur * 10 + i;
            } else {
                sum += cur * sign;
                cur = i;
                if (op == '+') {
                    sign = 1;
                } else {
                    sign = -1;
                }
            }
        }
        sum += cur * sign;
        if (sum == 0) {
            res.push_back(s);
        }
        return;
    }

    for (auto &c : ops) {
        s.push_back(c);
        dfs(i + 1);
        s.pop_back();
    }
}

int main() {
    ifstream fin("zerosum.in");
    ofstream fout("zerosum.out");
    fin >> N;
    dfs(1);
    sort(res.begin(), res.end());
    for (auto &result : res) {
        for (int i = 1; i < N; ++i) {
            fout << i << result[i - 1];
        }
        fout << N << endl;
    }
}