[프로그래머스] 타겟넘버 [C++]

---

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

---

발상

처음에 문제를 보고, 어떻게 하면 이걸 DFS로 풀수 있을까? 많이 고민을 했는데, 문제를 보니 '-'의 위치가 점차 뒤로가는 것을 보고 숫자를 벡터에 저장한다음 부호만 바꿔가면서 점차 진행하면 되지 않을까? 생각했다.

---

소스코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int answer = 0;

void DFS(int _size,int num,const vector<int>& number,int target)
{
    if (_size == number.size())
    {
        if (num == target)
            answer++;
    }
    else
    {
        DFS(_size + 1,num + number[_size],number,target);
        DFS(_size + 1,num - number[_size],number, target);
    }
}

int solution(vector<int> numbers, int target) {
    DFS(0, 0, numbers,target);
    return answer;
}