Replace operators of equation, so that the sum is equal to zero

Question

I'm given the equation like this one:

n = 7
1 + 1 - 4 - 4 - 4 - 2 - 2

How can I optimally replace operators, so that the sum of the equation is equal to zero, or print  -1. I think of one algorithm, but it is not optimal. I have an idea to bruteforce all cases with complexity O(n*2^n), but (n < 300).

Here is the link of the problem: http://codeforces.com/gym/100989/problem/M.

Answer 1

Here is the implementation in C++:

unordered_map <int, int> M, U;
unordered_map<int, int>::iterator it;
int a[] = {1, -1, 4, -4};

int solve() {
    for(int i = 0; i < n; ++i) {
        if(i == 0) M[a[i]] = 1;
        else {
            vector <pair <int, int>> vi;
            for(it = M.begin(); it != M.end(); ++it) {
                int k = it->first, d = it->second;
                vi.push_back({k + a[i], d});
                vi.push_back({k - a[i], d + 1});
            }
            for(int j = 0; j < vi.size(); ++j) M[vi[j].first] = MAXN;
            for(int j = 0; j < vi.size(); ++j) {
                M[vi[j].first] = min(M[vi[j].first], vi[j].second);
            }
        }
    }
    return (M[0] == 0 ? -1 : M[0] - 1);
}