[백준] 17610 / 양팔저울

// 프리셋 생략
#include <iostream>
#include <vector>

using namespace std;

int k, s;
int g[15];
vector<bool> able;

void DFS(int Idx, int wei)
{
    if (Idx == k)
    {
        if (wei >= 0)
            able[wei] = true;
        return;
    }

    DFS(Idx + 1, wei);
    DFS(Idx + 1, wei + g[Idx]);
    DFS(Idx + 1, wei - g[Idx]);
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> k;
    for (int i = 0; i < k; i++)
    {
        cin >> g[i];
        s += g[i];
    }
    able.resize(s + 1, false);

    DFS(0, 0);

    int ans = 0;
    for (int i = 1; i <= s; i++)
    {
        if (able[i] == false)
        {
            ans++;
        }
    }
    cout << ans << endl;
}