(프로그래머스 c++)타겟 넘버

dfs를 이용하여 문제를 풀어야 한다.

형태는

void dfs(vector<int>& numbers, int target, int sum, int count)

이다.

 

처음 시작할 때는 sum은 0, numbers의 인덱스를 0으로 시작한다.

 

dfs 내부)

우선 종료 조건을 선언하자.

numbers의 익덱스를 나타내는 count가 numbers.size()인지 확인하면 된다.

그리고 현재 sum이 target과 같으면 answer++을 해주고 return을 시키면 알아서 카운팅이 된다.

 

만약 count가 numbers.size()보다 작다면 계속 탐색을 해야한다.

현재 sum에 + numbers[count]와 - numbers[count]를 하여 target과 같은지 탐색하면 끝..!

#include <string>
#include <vector>

using namespace std;

int answer = 0;

void dfs(vector<int>& numbers, int target, int sum, int count)
{
    if(count == numbers.size())
    {
        if(sum == target)
            answer++;
        return;
    }
    dfs(numbers, target, sum + numbers[count], count + 1);
    dfs(numbers, target, sum - numbers[count], count + 1);
}

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