ProblemSolving/Programmers_TargetNumber_DFS.cpp at main · shinbian11/ProblemSolving · 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
#include <bits/stdc++.h>

using namespace std;

//ÇÁ·Î±×·¡¸Ó½º - Å¸°Ù ³Ñ¹ö (DFS)

int total;

void DFS(vector<int> numbers, int target, int sum, int n)
{
    if (n >= numbers.size())
    {
        if (sum == target)
            total += 1;
        return;
    }

    DFS(numbers, target, sum + numbers[n], n + 1);
    DFS(numbers, target, sum - numbers[n], n + 1);
}

int solution(vector<int> numbers, int target) {

    int answer = 0;

    DFS(numbers, target, numbers[0], 1);
    DFS(numbers, target, -numbers[0], 1);

    answer = total;

    return answer;
}