프로그래머스 / 타겟 넘버

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

프로그래머스

 

DFS/BFS로 해결이 가능하다

DFS로 해결했다

DFS를 재귀로 사용할 때 반드시 종료 조건이 있어야 한다

 

#include <string>
#include <vector>

using namespace std;

void dfs(int depth, int sum, vector<int>& numbers, int& answer, int target)
{
    // 모든 숫자를 사용한 경우
    if (depth == numbers.size())
    {
        // 연산한 값이 target과 같으면
        if (sum == target)
        {
            // answer 증가
            answer++;
        }
    }

    // dfs 순회
    if (depth < numbers.size())
    {
        // 숫자 더하기
        dfs(depth + 1, sum + numbers[depth], numbers, answer, target);
        // 숫자 빼기
        dfs(depth + 1, sum - numbers[depth], numbers, answer, target);
    }
}

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

    dfs(0,0,numbers,answer, target);

    return answer;
}