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

문제 링크

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

프로그래머스

 

코드 구현

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

using namespace std;

int answer = 0;

void dfs(const vector<int>& numbers, int _Index, int _sum, const int& _target)
{
    if (_Index == numbers.size())
    {
        if (_sum == _target) answer++;
        return;
    }
      
    dfs(numbers, _Index + 1, _sum + numbers[_Index], _target);
    dfs(numbers, _Index + 1, _sum - numbers[_Index], _target);
}

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

    return answer;
}

 

 

해결 방법

모든 경우의 수를 순회하도록 재귀 함수를 이용한 DFS 알고리즘을 사용하였다.