[ 구름 / DFS ] 양팔 저울

1. 문제

---

 

17610번: 양팔저울

 

2. 소스코드

---

 

#include <iostream>
#include <vector>
using namespace std;
vector <bool> weigh(2600001, false);
int k;
void dfs(int a[], int p, int sum)
{
    if (p > k)
    {
        if (sum < 0) return;
        weigh[sum] = true;
    }
    else
    {
        dfs(a, p + 1, sum - a[p]);
        dfs(a, p + 1, sum);
        dfs(a, p + 1, sum + a[p]);
    }
}
int main()
{
    int x = 0;
    cin >> k;
    int v[15];
    for (int i = 1; i <= k; i++)
    {
        cin >> v[i];
        x += v[i];
    }
    dfs(v, 1, 0);
    int y = 0;
    for (int i = 1; i <= x; i++)
        if (!weigh[i]) y++;
    cout << y;
}