[프로그래머스] 코딩테스트 연습 타겟 넘버 풀이 C++ 소스 코드

프로그래머스 코딩테스트 연습문제 깊이/너비 우선 탐색(DFS/BFS) 타겟 넘버 풀이입니다.

저는 재귀함수로 DFS를 구현해서 풀었습니다. 제 풀이가 완벽한 정답은 아닐 수 있으니 참고만 해주세요.

#include <string>
#include <vector>

using namespace std;
int answer = 0;

void DFS(vector<int> v, int size, int target, int depth, int *flag) {
    int s = 0;
    if(depth == size) {
        for (int i = 0; i < size; i++) {
			if (flag[i] == 1) s += v[i];
            else if(flag[i] == 0) s -= v[i];
		}
        if(s == target) answer++;
        return;
    }
	flag[depth] = 1; DFS(v, size, target, depth + 1, flag);
	flag[depth] = 0; DFS(v, size, target, depth + 1, flag);
}

int solution(vector<int> numbers, int target) {
    int *flag = new int[numbers.size()]();
    DFS(numbers, numbers.size(), target, 0, flag);
    return answer;
}