프로그래머스 - 타겟 넘버 - Level 2

문제

풀이전략

1. DFS를 사용하여 +, - 들을 다 넣어가며 계산해본다.

코드

#include <string>
#include <vector>

using namespace std;

int answer = 0;

void DFS(int L, vector<int> num, int mySum, int ttt){
    if(L == num.size()){
        if(mySum == ttt) answer++;
        return;
    }
    else{
    	// 숫자를 더해주는 부분
        DFS(L+1, num, mySum+num[L], ttt);
        // 숫자를 빼주는 부분
        DFS(L+1, num, mySum-num[L], ttt);
    }
    
}

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

소감

간단한 DFS 문제였다.