프로그래머스 타겟 넘버 문제풀이

문제를 보고 DFS 를 이용하여 풀려고 했으나

또 순서를 생각해서 풀려고 하여 헷갈렸다.

내가 아니라 컴퓨터가 돌리게 하자

문제는 간단하였다. dfs 함수에서 numbers 에 있는 숫자들을 

더하기 , 빼기 연산을 했을때 연산횟수가 cnt 와 같아질때 그 값들이 target 과 같았을 때 

answer 을 1을 더해주면 된다.

 

#include <string>
#include <vector>
int answer=0;
using namespace std;
void dfs(vector<int>numbers,int tg, int sum, int cnt){
    if(cnt==numbers.size()){
         if(sum==tg)answer++;
        return;
    }
    dfs(numbers, tg, sum + numbers[cnt], cnt + 1);
    dfs(numbers, tg, sum - numbers[cnt], cnt + 1);
}
int solution(vector<int> numbers, int target) {
    dfs(numbers,target,0,0);
    return answer;
}