problem-solving/BOJ_1208.cpp at main · junhee-won/problem-solving · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 21 / 12 / 31

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int n, s;
long long answer;
vector<int> arr;
map<int, int> m;

void dfsLeft(int level, int sum)
{
    if (level == arr.size() / 2)
    {
        return;
    }

    m[sum + arr[level]]++;
    dfsLeft(level + 1, sum + arr[level]);
    dfsLeft(level + 1, sum);
}

void dfsRight(int level, int sum)
{
    if (level == arr.size())
        return;

    int x = sum + arr[level];
    answer += m[s - x];
    dfsRight(level + 1, x);
    dfsRight(level + 1, sum);
}

int main(void)
{
    cin >> n >> s;
    arr.assign(n, 0);
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    dfsLeft(0, 0);
    answer += m[s];
    m[0]++;
    dfsRight(arr.size() / 2, 0);

    cout << answer;

    return 0;
}