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

#include <string>
#include <vector>
#include <queue>

using namespace std;

int result = 0;

void DFS(vector<int> numbers, int target, int sum, int count);

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

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

 

풀이

1. 숫자를 모두 사용하여 수식을 완성한다.
2. 숫자를 모두 사용했을때 총합이 target과 같은지 확인한다.
3. 같다면 몇개인지 하나씩 추가해준다.