[白俊]1760/両腕秤

/*
 * Problem :: 17610 / 양팔저울
 *
 * Kind :: Brute Force + DFS
 *
 * Insight
 * - {1, 2, 6}, S=9 라면,
 *   4 = 6-2 로
 *   5 = 6-1 로 구할 수 있다
 *   + 즉, 무게 x 를 구하는데 추를 더하거나 빼거나 사용하지 않을 수 있다
 *     # max(추의 개수)=13, O(3^13) = 1594323 < O(10^8)
 *       모든 경우의 수를 다 해봐도 시간 내에 해결할 수 있을 것 같다
 *
 * Point
 * - DFS 로 가능한 모든 경우를 순회했다
 *   + Bitmask 로 순회할 수도 있지만
 *     3진수로 바꾸는 게 귀찮았다... (헤헤)
 */

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <vector>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int K;
int G[13];
int S;
vector<bool> canMeasure;

// Set up : Functions Declaration
void f(int idx, int weight);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    cin >> K;
    for (int i=0; i<K; i++) {
        cin >> G[i];
        S += G[i];
    }

    // Process
    canMeasure.resize(S+1, false); /* 무게를 잴 수 있는지 여부를 저장하는 전역 배열 초기화 */
    f(0, 0);

    // Control : Output
    int ans = 0;
    for (int i=1; i<S; i++) {
        if (not(canMeasure[i])) { ans++; }
    } cout << ans << endl;
}

// Helper Functions
void f(int idx, int weight)
/* 현재 idx 번째 추를 사용해서 weight 무게를 잰 상태 */
{
    if (idx == K) { /* 가능한 경우 중 하나를 찾았을 때 <= 모든 추의 사용여부가 결정됨 */
        if (weight > 0) { /* 현재까지 측정한 무게가 양수이면 */
            canMeasure[weight] = true; /* 그 무게를 측정할 수 있음 */
        } return;
    }

    f(idx+1, weight); /* 현재 추를 사용하지 않음 */
    f(idx+1, weight+G[idx]); /* 현재 추를 무게를 더하는 데 사용 */
    f(idx+1, weight-G[idx]); /* 현재 추를 무게를 빼는 데 사용 */
}